🚡Next Permutation / Previous Permutation

Intro

1) Next Permutation

★ Combinatorics 조합론에서 흔히 볼 수 있는 대표 알고리즘 중 하나로, print the lexicographically next greater permutation of the given array. If there does not exist any greater permutation, then print the lexicographically smallest permutation of the given array.

 

★ 배열에 여러 수가 정렬되어 있다면, 사전 순으로 그 다음 수, 즉 현재 수보다 크되 큰 수 중 가장 작은 수를 구하는 알고리즘. 현재 수보다 큰 수가 존재하지 않는다면 permutation 중 가장 작은 수를 구함.

 

★ 예를 들어, 241750의 next permutation은 245017. 123의 next permutation은 132. 321의 next permutation은 존재하지 않으므로 가장 작은 permutation인 123

 

2) Previous Permutation

★ 위 Next Permutation의 반대 개념으로, printing the lexicographically before permutation of the given array.

 

★ 배열에서 사전 순으로 바로 앞에 오는 직전 수를 구하는 알고리즘.

 

★ 예를 들어 241750의 previous permutation은 241705. 123의 previous permutation은 존재 x.

Approah

1) Next Permutation

① Brute-force 접근법: 주어진 수의 조합으로 찾을 수 있는 모든 permutation을 구해서 내가 원하는 permutation을 뽑는 접근법. 가능한 모든 수의 permutation을 일일이 만드는데 O(N!). 그리고 각각의 permutation이 내가 원하는 permutation인지 확인하는 과정이 O(N). 따라서 최종 시간복잡도는 O(N*N!)

 

② linear-search: 시간복잡도 O(N)

(1) 숫자로 이루어진 arr 준비

(2) 🚡 오른쪽부터 왼쪽으로 역으로 진행하면서 pivot 찾기(non-increasing하지 않는 지점): while문

 

(3) pivot index가 0이상이라면: next permutation 존재

→ 🚡 rightmost successor(pivot보다 크거나 같은 원소 / pivot 오른쪽에서) 구하기: while문

→ pivot과 successor swap

→ pivot 이후(pivot 포함 x) reverse sort

 

(4) pivot index가 0미만이라면: next permutation 존재 x. 전체 sort해서 가장 작은 permutation return

---

2) Previous Permutation

 

(1) 숫자로 이루어진 arr 준비

(2) 🚡 오른쪽부터 왼쪽으로 역으로 진행하면서 pivot 찾기(non-decreasing하지 않는 지점): while문

 

(3) pivot index가 0이상이라면: next permutation 존재

→ 🚡 rightmost successor(pivot보다 작거나 같은 원소 / pivot 오른쪽에서) 구하기: while문

→ pivot과 successor swap

→ pivot 이후(pivot 포함 x) reverse sort

 

(4) pivot index가 0미만이라면: next permutation 존재 x. 전체 sort해서 가장 작은 permutation return

 

★ Previous Permutation은 Next Permutation에서 pivot인 i와 right successor j를 구하는 과정에서 부등식만 기호를 바꾸면 됨 ★

Code

1) Next Permutation

def next_permutation(n,l): #O(N)
    i = l-2
    while i >=0 and n[i] >= n[i+1]: #find the pivot
        i-=1  

    if i>=0: #if pivot, swap 
        j = l-1
        while n[j] <= n[i]: #fine rightmost successor
            j-=1
        n[i],n[j] = n[j],n[i] #swap
        n[i+1:] = reversed(n[i+1:]) #reverse the suffix
        return n
    else: #if no pivot, return the first permutation
    	n.sort()
        return n

 

2) Previous Permutation

def previous_permutation(n,l):
    i = l-2
    while i>=0 and n[i] <= n[i+1]:
        i -= 1
    if i>=0:
        j = l - 1
        while n[j] >= n[i]:
            j -= 1
        n[i],n[j]=n[j],n[i] #swap
        n=n[:i+1]+sorted(n[i+1:],reverse=True)
        return n
    else: #if no pivot, this is the first permutation
        return -1

Examples

🚡 <BOJ S2 5360 - Next Permutation>

Q. Next permutation 구하면 출력, 없다면 USELESS!

 

🚡 <BOJ S2 2697 - 다음수 구하기>

Q. 위와 동일, 다만 없다면 BIGGEST

 

🚡 <BOJ S3 10972 - 다음 순열>

Q, Next permutation 구하면 구성 숫자 순서대로 출력, 없다면 -1

 

🚡 <BOJ S3 10973 - 이전 순열>

Q. 10972 Next 대신 Previous permutation 구하기

---

geeksforgeeks

chatgpt