[Python] Next Permutation, Previous Permutation

• 사전순으로 다음에 오는 순열을 찾는 방법

1. A[i-1] < A[i]를 만족하는 가장 큰 i를 찾는다

2. j >= i이면서 A[j] > A[i-1]를 만족하는 가장 큰 j를 찾는다

3. A[i-1]과 A[j]를 swap한다

4. A[i]부터 순열을 뒤집는다

 

(1) A[i-1] < A[i]를 만족하는 가장 큰 i를 찾는다

 i = len(a)-1
    while i > 0 and a[i-1] >= a[i]:
        i -= 1

 

(2) j >= i이면서 A[j] > A[i-1]를 만족하는 가장 큰 j를 찾는다

j = len(a)-1
   while a[j] <= a[i-1]:
       j -= 1

 

(3) A[i-1]과 A[j]를 swap한다

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

 

(4) A[i]부터 순열을 뒤집는다

 while i < j:
        a[i],a[j] = a[j],a[i]
        i += 1
        j -= 1

 

• 전체코드

def next_permutation(a):
    i = len(a)-1
    while i > 0 and a[i-1] >= a[i]:
        i -= 1
    if i <= 0:
        return False
    j = len(a)-1
    while a[j] <= a[i-1]:
        j -= 1
    a[i-1],a[j] = a[j],a[i-1]
    j = len(a)-1
    while i < j:
        a[i],a[j] = a[j],a[i]
        i += 1
        j -= 1
    return a

• 다음 순열을 구하는 시간 복잡도는 O(N)이고, 전체 순열을 모두 구하는
  시간 복잡도는 O(N! * N)이다.

 
 
 
 

• 똑같은 원리로 사전순으로 이전에 오는 순열도 찾을 수 있다.

def prev_permutation(a):
    i = len(a)-1
    while i > 0 and a[i-1] <= a[i]:
      i -= 1
    if i <= 0:
       return False
    j = len(a)-1
    while a[j] >= a[i-1]:
        j -= 1
    a[i-1],a[j] = a[j],a[i-1]
    j = len(a)-1
    while i < j:
        a[i],a[j] = a[j],a[i]
        i += 1
        j -= 1
    return a