[Python] 순열 알고리즘

다음 순열 구하는 알고리즘

1. A[i-1] < A[i] 를 만족하는 가장 큰 i 를 찾는다.
2. i <= j 이면서 A[j] > A[i-1]를 만족하는 가장 큰 j 를 찾는다.
3. A[i-1] 과 A[j]를 SWAP 한다
4. A[i] 부터 순열을 뒤집는다.

def next_perm(a):
    i = len(a)-1

    # 1번
    while i > 0 and a[i-1] >= a[i]: 
        i -= 1

    # 더이상 다음 순열을 구할 수 없음 = False 리턴
    if i <= 0:    
        return False

    # 2번
    j = len(a)-1
    while a[i-1] >= a[j]:            
        j -= 1

    # 3번
    a[i-1], a[j] = a[j], a[i-1]        

    # 4번
    j = len(a)-1
    while i < j:
        a[i], a[j] = a[j], a[i]        
        i += 1
        j -= 1

    return True

a = [2,3,1,7,6,5,4]
next_perm(a)
print(a) # [2,3,4,1,5,6,7]