next_permutation Python 구현

def next_permutation(arr):
    i,j = len(arr)-1, len(arr)-1

    while i>0 and  arr[i-1]>=arr[i]:
        i-=1

    if i==0:
        return False

    while arr[i-1]>=arr[j]:
        j-=1

    arr[i-1], arr[j] = arr[j],arr[i-1]

    k = len(arr)-1

    while i<k:
        arr[i],arr[k] = arr[k],arr[i]
        i+=1
        k-=1
    return arr 

 

Next permutation 은 다음과 같이 구현할 수 있다.

1. arr[i-1] >= arr[i] 가 되는 i 중 제일 큰 값을 찾는다.
   1. i 가 0 이 되면 [5,4,3,2,1] 같이 역으로 정렬되어있는 값이라 순열의 끝이라 False 를 반환한다.
2. arr[i-1] >= arr[j] 가 되는 j 중 가장 큰 값을 찾는다.
   
   1. 이 때, 1 번에서 arr[i-1] >= arr[i] 를 찾았기 때문에 무조건 i<j 이다.
3. arr[i],arr[j]를 바꿔준다.
4. arr의 i 번째부터 끝까지의 원소를 뒤집는다.