Next Permutation 알고리즘

임의의 수열 {a_n}의 모든 원소의 순서를 뒤섞어 새로운 수열 {b_n}을 만드는 것을 순열(Permutation)이라 한다.

{a_n}의 Next Permutation이란 다음 순열,

즉 {a_n}의 모든 원소의 순서를 뒤섞어 만들 수 있는 모든 수열들을 사전순으로 나열할 때 {a_n}의 다음에 오는 수열을 가리킨다.

 

5개의 원소를 가진 집합 {1, 2, 3, 4, 5}의 원소를 한 번씩만 사용하여 구성할 수 있는 모든 수열을 사전순으로 나열한 일부를 통해 규칙을 발견해 보자.

[1, 2, 3, 4, 5]
...
[3, 5, 4, 1, 2]
[3, 5, 4, 2, 1]
[4, 1, 2, 3, 5]
[4, 1, 2, 5, 3]
[4, 1, 3, 2, 5]
[4, 1, 3, 5, 2]
[4, 1, 5, 2, 3]
[4, 1, 5, 3, 2]
[4, 2, 1, 3, 5]
[4, 2, 1, 5, 3]
[4, 2, 3, 1, 5]
[4, 2, 3, 5, 1]
[4, 2, 5, 1, 3]
[4, 2, 5, 3, 1]
[4, 3, 1, 2, 5]
...
[5, 4, 3, 2, 1]

가장 첫 순열은 [1, 2, 3, 4, 5]이고 가장 마지막 순열은 [5, 4, 3, 2, 1]이다.

즉 순열을 사전 순으로 배열하는 것은 오름차순으로 배열된 순열을 내림차순으로 배열해 가는 과정으로 볼 수 있다.

 

[4, 2, 5, 1, 3]의 다음 순열을 찾는 과정을 보자.

[ 4 ↘️ 2 ↗️ 5 ↘️ 1 ↗️ 3 ]

이때 가장 마지막의 오름차순 조각인 [ 1 ↗️ 3 ] 부분을 내림차순으로 배열하기 위해 1과 3의 순서를 바꾸어 주면

[ 4 ↘️ 2 ↗️ 5 ↘️ 3 ↘️ 1 ]

[4, 2, 5, 1, 3]의 다음 순열 [4, 2, 5, 3, 1]을 얻을 수 있다.

 

이제 뒤에서부터 [ 5 ↘️ 3 ↘️ 1 ] 부분이 내림차순으로 정렬되었고,

가장 마지막 오름차순 조각은 [ 2 ↗️ 5 ↘️ 3 ↘️ 1 ]이 된다.
다음 순열을 구할 때 현재 2의 위치에는 2보다 큰 수가 와야 하는데, [ 5 ↘️ 3 ↘️ 1 ] 부분은 내림차순으로 정렬되어 있으므로

뒤에서부터 탐색하여 3이 2보다 큰 최솟값임을 알 수 있다.

이제 3과 2의 순서를 바꾸어 주면

[ 4 ↘️ 3 ↗️ 5 ↘️ 2 ↘️ 1 ]

위와 같이 3의 뒷부분은 항상 내림차순이 유지된다.

 

[ 4 ↘️ 3 ... ]으로 시작하는 가장 첫 순열은 3의 뒷부분이 오름차순으로 정렬되어야 하므로

[5, 2, 1]을 [1, 2, 5]과 같이 역순으로 정렬해 주자.

[ 4 ↘️ 3 ↘️ 1 ↗️ 2 ↗️ 5 ]

이렇게 [4, 2, 5, 3, 1]의 다음 순열인 [4, 3, 1, 2, 5]를 구할 수 있다.

 

이 과정을 일반화하면 다음과 같다.

1. 수열 {a_n}의 내림차순으로 정렬된 뒷부분을 찾는다.
2. a_i+1부터 a_n까지 모두 내림차순으로 정렬되어 있다면, 수열의 가장 마지막 오름차순 조각은 a_i ↗️ a_i+1이다.
3. a_i+1 ≥ a_i+2 ≥ ... ≥ a_k > a_i ≥ a_k+1 ≥ ...  a_n을 만족하는 a_k를 찾는다. 즉, a_i보다 큰 최솟값 a_k를 찾는다.
4. a_i의 자리에 a_k를 넣어 준다. 이때 a_i와 a_k의 자리를 교환하면 뒷부분이 내림차순으로 유지된다.
5. 내림차순인 뒷부분을 역순(오름차순)으로 바꾸어 준다.