[Next Permutation] 순열의 다음 번 순서 구하기

• 가독성이 더 좋은 Notion Posting

---

◾ Introduction 

리스트에 대해서 순서를 바꾸는 Permutation은 총 $n!$ 개가 가능하기에 임의의 원소들에서 다음 Permutation 순서를 구하기 위해서 처음부터 순열을 시작할 경우, 최악의 경우 $O(n!)$ 의 시간복잡도를 가지게 된다. 이러한 비효율을 해결하기 위해서, 기존 순열에서 다음 순열을 구하는 next_permutation 알고리즘이 필요하다.

---

◾ 예시를 통한 설명 

예시를 통해서 next_permutation 알고리즘의 원리를 살펴보자.

1 5 8 4 7 6 5 2 1

그림으로 나타낸다면 오른쪽과 같은 형태를 띈다. 여기서 next_permutation 은 다음으로 큰 숫자를 나타내므로 4 의 위치에 5 가 앞으로 나가고, 나머지 숫자들이 오름차순으로 정렬되면 된다. 그 이유는 4 보다 뒤에 있는 숫자들이 이미 가장 큰 (7, 6, 5, 2, 1) 형태를 띄고 있기 때문이다.

---

◾ Algorithm 

1. $a[i-1]$ 이 $a[i]$ 보다 작은 $i$ 를 찾는다.
2. 뒷 부분에 있는 수 중에서 하나를 선택한다.
3. $a[i-1]$ 뒷 부분에 있는 수와 자리를 바꾼다.
4. 뒷 부분을 오름차순📈으로정렬한다.

여기서 뒷 부분에 있는 수는 next_permutation 을 만들어야 하므로, 현재 순열보다 큰 것 중들 중에서 가장 작은 것을 만들도록 선택되어야 한다.

예시로 9 와 (10, 11, 4 5, 12) 가 있다면 10과 자리를 바꿔야 한다.

---

Next_permutation Algorithm Example

1. (4, 7, 6, 5, 4, 3, 2, 1) # 시작
2. (5, 7, 6, 4, 4, 3, 2, 1) # Swap
3. (5, 1, 2, 3, 4, 4, 6, 7) # Sort

😋 처음 4의 위치는 이제 관심없다. (3)

 

---

🐍 Implementation   

앞부분에 위치한 작은 수를 swap_small 으로 명하고 이 숫자와 자리 바꿀 수를 swap_large 로 명했다. 주의사항은 이미 최대순열이라면 swap을 하지 않고 종료하는 것이다.

def next_permutation(lst):

        # 1. find swap_small
    swap_small = len(lst)-2
    while lst[swap_small] >= lst[swap_small+1]: # pass if monotonic increasing
        swap_small -=1
        if swap_small ==-1:  # no swap! already the last permutation
        return

        # 2. find swap_large
    swap_large = start+1
    MIN = lst[swap_large] 
    for i in range(swap_large, len(lst)):
        if lst[i] < MIN and lst[i] > lst[swap_small]:
            MIN = lst[i] 
            swap_large = i

    # 3. swap
    lst[swap_small], lst[swap_large] = lst[swap_large], lst[swap_small]

        # 4. sort 
    revserse_list = sorted(lst[swap_small+1:], reverse=False)
    for i in range(len(lst)-swap_small-1):
        lst[swap_small+1+i] = revserse_list[i]

---

◾References

[1] Origial post link : https://leetcode.com/problems/next-permutation/

---