[알고리즘]Next Permutation 알고리즘

Next Permutation Algorithm은 순열 알고리즘 중에 하나로 무작위 순열의 다음 순열을 구하는 알고리즘입니다.

시간 복잡도는 O(N)이고 Greedy 알고리즘을 기반으로 합니다.

아래의 수열을 예로 다음에 올 순열을 구해보겠습니다.

5가지의 무작위 숫자가 주어지고 이를 N 배열에 저장합니다.

Greedy를 이용하여 N[i] < N[i + 1]을 만족하는 가장 마지막 i를 구합니다. 이 때, 만족하는 i가 없다면 해당 순열이 가장 마지막 순열임을 의미합니다.

i를 구했으면 배열의 마지막부터 i까지 순회하면서 N[j] > N[i]를 만족하는 j값을 구합니다.

바로 직전 반복문에서 N[i] < N[i + 1]을 만족했기 때문에 j는 최소한 하나는 무조건 존재합니다.

j를 찾았으면 N[i]와 N[j]를 swap합니다.

그 이후, i + 1 번째부터 배열의 끝까지 reverse 해주면 됩니다.

최종적으로, answer = n[:x + 1] + n[:x:-1]로 답을 구할 수 있습니다.

코드

def next_permutation(lst):
    l = len(lst)
    x = -1  # highest index
    for i in range(l - 2, -1, -1):
        if lst[i] < lst[i + 1]:
            x = i
            break
    if x == -1:
        return -1  # 다음 순열이 없다는 것을 의미
    for j in range(l - 1, 0, -1):
        if lst[j] > lst[x]:
            lst[x], lst[j] = lst[j], lst[x]
            break
    return lst[:x + 1] + lst[:x:-1]


s = [2, 5, 1, 9, 7]
print(next_permutation(s))

# [2, 5, 7, 1, 9]

 

Ref.

https://jins-dev.tistory.com/entry/%EB%8B%A4%EC%9D%8C-%EC%88%9C%EC%97%B4-%EC%B0%BE%EA%B8%B0-%EC%A0%84%EC%B2%B4-%EC%88%9C%EC%97%B4-%ED%83%90%EC%83%89-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Next-Permutation

다음 순열 찾기 / 전체 순열 탐색 알고리즘 (Next Permutation)