순열 next_permutation()과 prev_permutation() 직접 구현하기

순열 next_permutation()과 prev_permutation() 직접 구현하기

다음 순열, 이전 순열, 모든 순열

 

순열

크기 n이 3인 수열을 사전순으로 나열하면 다음과 같다

123
132
213
231
312
321

n=3인 수열은 총 6개가 있다

여기서 먼저 알 수 있는 사실은 크기가 n인 순열을 총 n!개 존재한다는 것이다

첫 번째 오는 수를 n가지 중에서 선택, 그 다음 수를 n-1가지 중에서 선택, 그 다다음 수를 n-2가지 중에서 선택..을 반복하기 때문에 총 가지 수는 n*(n-1)*(n-2)*...*2*1 즉, n!이다

 

또 알 수 있는 사실은 첫 순열은 오름차순, 마지막 순열은 내림차순이라는 것이다

그러므로 중간 순열을 구하고 싶다면 첫 순열에서 다음, 다음, 다음으로 넘어가서 맨 마지막 내림차순이 될 때까지 반복하면 된다

여기서 우리는 중간 수열을 구하기 위해서 다음 순열을 구하면 된다는 사실을 알 수 있다

 

다음 순열

순열을 사전순으로 나열했을 때, 사전순으로 다음에 오는 순열과 이전에 오는 순열을 찾는 방법

 

C++ STL의 algorithm에는 이미 next_permutation과 prev_permutation이 존재하기 때문에 사용하면 된다

하지만 해당 라이브러리는 자바에는 없고, 파이썬에는 itertools에 비슷한 것이 있지만 약간 부족한 면이 있다

라이브러리를 사용한다고 해도 내부 구조를 알고 있어야 잘 쓸 수 있기 때문에 직접 구현을 한 번 해 본다

 

다음 순열을 구하는 방법은 다음 4가지 과정을 거친다

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

또한 순열: 7 2 3 6 5 4 1 이 있다고 가정한다

 

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

즉, 순열의 마지막 수에서 끝나는 가장 긴 감소수열을 찾는다

 

마지막 순열이 내림차순이므로 어떤 순열을 내림차순 정렬로 만드는 과정이 필요하며, 그 과정들이 중간 순열이라고 생각하면 된다

내림차순이 아닌 부분을 swap하기 위해 어느 부분을 swap할 것인지를 찾는다

좀 더 구체적으로 말하면 > 방향이 나오지 않는 가장 큰 i를 찾는다

 

예시 순열에서는 6 5 4 1까지는 내림차순이었는데, 3에서 내림차순에 어긋났다

이 때 6의 위치를 i, 3의 위치를 i-1이라고 한다

 

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

이제 7 2 ? 로 시작하는 첫 순열을 찾아야 한다

i부터 오른쪽으로 가면서 3보다 크면서 가장 작은 수를 찾아보니 4가 있다

이제 4의 위치를 j라고 한다

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

i-1인 3과 j인 4를 swap한다

7 2 4 6 5 3 1이 되었다

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

이제 7 2 4의 뒷 순열인 6 5 3 1 부분은 첫 순열이 되어야 하니까 뒤집는다

7 2 4 1 3 5 6이 되었다

 

다음 순열은 7 2 4 1 3 5 6 이다

시간 복잡도는 1번에서 O(N), 2번에서 O(N), 3번은 O(1), 4번에서 O(N)이 걸려 총 O(N+N+1+N)=O(3N+1)=O(N) 이다

 

다음은 C++ 코드로 구현한 next_permutation() 이다

bool next_permutation(vector<int> &a, int n){
	int i = n - 1;
	while (i > 0 && a[i - 1] >= a[i]) i -= 1; //뒤에서 앞으로 가면서 i-1>=i가 아니면 끝(1번)
	if (i <= 0) return false; //만약 마지막 순열이라면 끝난다
	int j = n - 1;
	while (a[j] <= a[i - 1]) j -= 1; //뒤에서 앞으로 가면서 크면서 가장 작은 수를 구한다(2번)
	swap(a[i - 1], a[j]); //두 수의 위치를 바꾼다 (3번)
	j = n - 1;
	while (i < j) { //i<n-1까지의 수열을 뒤집는다 (4번)
		swap(a[i], a[j]);
		i += 1; j -= 1;
	}
	return true; //다음 수열이 존재한다 true
}

github.com/proqk/Algorithm/blob/master/BruteForce/10972%20%EB%8B%A4%EC%9D%8C%20%EC%88%9C%EC%97%B4.cpp

 

C++ std algorithm의 next_permutation()으로 구현하면 이렇게 된다

if (next_permutation(a.begin(), a.end())) {
	for (int i = 0; i < n; i++) cout << a[i] << ' ';
}

 

이전 순열

이전 순열은 다음 순열을 구한 과정에서 모든 부분을 반대로 하면 된다

bool prev_permutation(vector<int> &a, int n){
	int i = n - 1;
	while (i > 0 && a[i - 1] <= a[i]) i -= 1; //(1번)
	if (i <= 0) return false;
	int j = n - 1;
	while (a[j] >= a[i - 1]) j -= 1; //(2번)
	swap(a[i - 1], a[j]); //(3번)
	j = n - 1;
	while (i < j) { //4번)
		swap(a[i], a[j]);
		i += 1; j -= 1;
	}
	return true;
}

github.com/proqk/Algorithm/blob/master/BruteForce/10973%20%EC%9D%B4%EC%A0%84%20%EC%88%9C%EC%97%B4.cpp

 

if (prev_permutation(a.begin(), a.end())) {
	for (int i = 0; i < n; i++) cout << a[i] << ' ';
}

 

모든 순열

모든 순열은 next_permutation()을 마지막 순열까지 계속 반복하면 된다

다만 주의할 점은 C++의 next_permutation 함수가 다음 순열이 있는지 검사할 뿐만 아니라, 다음 순열을 만들기도 하기 때문에 while문으로 하면 첫순열을 빼먹게 된다

그래서 모든 순열을 구하는 경우에만 특별하게 do-while으로 구현을 한다

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL);
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++) a[i] = i + 1;
	do {
		for (int i = 0; i < n; i++) cout << a[i] << ' ';
		cout << '\n';
	} while (next_permutation(a.begin(), a.end()));
}

참고로 중복 순열의 경우도 next_permutation() 구현할 때 같거나~를 조건으로 주었기 때문에 똑같은 코드로 처리할 수 있다