4 min to read

C++ STL next_permutation의 구현

수열을 만들어내는 함수 next_permutation을 직접 구현 해보자!

Featured image

next_permutaion이 뭔데?

특정한 수열의 가능한 배열 중에 입력으로 들어온 수열을 사전순(lexicographic)으로 마지막이 될 때까지 순회를 시켜서 마지막이면 false 를 리턴하고 사전순으로 가장 처음인 순서대로 주어진 수열을 만들어 놓는다.

사전순으로 마지막인것의 평가는?

간단하게 말해서 내림차순으로 정렬되어 있는지를 알아보면 된다. 이를 보다 엄밀히 정의를 하자면 수열 A가 n개의 수로 이루어진 수열이라고 할 때, 0부터 n-1까지의 모든 자연수 k에 대헤서 \(A[k] \ge A[k+1]\)가 성립하면 된다. 너무나 간단한것 같지만, 수열의 순열을 사전순으로 만들어야 할 때는 이 정의를 활용해서 생각을 해 볼 것이니, 간단하므로 이해 해보자.

간략하게나마 미리 설명하자면, \(A[k] < A[k+1]\) 이 성립하는 k가 있으면 오름차순을 깨는 것으로 A[k] 부터 수열 끝까지에 있는 수들의 순서를 조작함으로 사전순으로 뒤에 있는 순열들을 만들어 낼 수 있으며, k가 클수록 뒷편에서 이 작업을 할 수 있다는 것인데, 이것이 중요한건 다음 장에서 조금 더 다루기로 하겠다.

“바로 다음 순서”의 수열 만들기

적당한 짧은 수열이면서 모든 원소가 다른’1 2 3 4’의 가능한 순열을 사전순으로 나열해 보도록 하자

우리가 이 수열들을 나열할 때 방법이 여러가지가 있겠지만, next_permutation을 더 잘 이해하기 위해서 아래의 방법대로 해보자.

  1. 오름차순으로 정렬된 본래의 수열부터 출발한다.
  2. 그 다음 수열로 넘어갈 때는, 다음 수와 오름차순 관계를 이루는 가장 뒤에 있는 수들 한쌍을 찾아서, 즉 앞서 간단히 말했던 \(A[k] < A[k+1]\) 이 성립하는 가장 큰 k를 찾고
  3. k보다 인덱스가 큰 수들 중에서, A[k]보다 큰 수를 찾고(이를 A[h]라고 하자)
  4. A[k]와 A[h]를 바꾼다음
  5. A[k+1]부터 끝까지의 부분 수열을 오름차순으로 정렬하자.

이것만 보자면 일단 따라 하면 사전순으로 다음 수열이 나오는것은 대강 알겠는데, 각 단계의 의미 같은것을 한번 짚고 넘어가자. 앞에서도 말했듯, 사전순으로 다음 순열을 찾는것은 오름차순을 깨트리는 과정인데, 오름차순이 깨지면, 앞쪽에 큰 원소가 오는것은 자명한 사실이다. 큰 원소가 앞으로 올 수록 사전순으로 뒤로 밀려난다.(2134와 3124를 생각해 보자) 우리는 한 단계씩 다음 사전순으로 넘기는것을 원하고, 필요 없이 많은 영향을 끼치는 것을 원치 않으므로, 가장 뒤에 있는것을 찾는다고 한것이다.

3번 과정에서 가장 최소의 수를 찾는것도, 이와 같은 맥락이다. 최대한 영향을 작게 주는 쪽으로 가보는것을 원하니… 여기서 k보다 인덱스가 크다는 조건을 달아놓은 이유는, 뒷쪽 부분 수열을 다음 수열로 만드는데 앞에 있는 수를 건드리면, 뒤쪽에 있는 수를 건드리는것보다 어느 방향이건 파급력이 커진다. (앞의 수를 건드릴수록, 건드리는 수의 크기가 클수록 영향이 큼은 자명한 사실이다. 이해가 잘 되지 않는다면 사전순의 정의를 곰곰히 생각해 보자)

5번 과정에서 다시 오름차순으로 정렬하는 과정 또한 같은 맥락이다. 뒷부분이 오름차순으로 정렬되 있는것과 오름차순이 아닌 방법으로 정렬되어 있는 것 중 사전순으로 앞에 있는것은 오름차순이 아닌가?

같은 원소가 있을때도 상관 없다. 위 과정에서 대소비교 만으로 모든것이 굴러가는데, 같은 원소가 있다고 해서, 딱히 문제 될 것은 없다.

코드상으로 위의 알고리즘을 구현할 때는 5번 과정에서 sort 함수를 쓰지 않는다. 일반적인 소팅 알고리즘은 \(O(NlgN)\)이나 \(O(N^2)\)의 시간복잡도를 가지는데,(카운팅 정렬이나, 기수 정렬 같은 정렬 알고리즘은 O(N)이거나 이에 근접한데, 공간 복잡도가 크다는 단점이 있다) 5번 과정에서 정렬해야할 부분 수열은 상대적으로 내림차순으로 정렬 되어 있기에 단순히 뒤집으면 되고, 이는 O(N)으로 구성 할 수 있다. 왜 내림차순 정렬인지 간단히 알아보도록 하자.

내림차순 정렬 여부 확인법

n개의 원소를 가진 A라는 이름의 수열을 일반적인 형태로 나타내보자.

A[0] A[1] … A[K] A[K+1] … A[H] … A[n-1] (이때, K와 H는 위에서 설명했던 2번과정과 3번 과정에 해당하는 그것이다.)

여기서 앞 장에서 2번의 가장 뒤에 있는수라는 조건에 의해 A[K+2]부터 A[n-1]까지의 부분 수열에서는 오름차순이 발견될 수 없다. 즉 내림차순으로 정렬되어 있는 상황으로 볼 수 있다. 이때 A[K]와 A[H]의 자리를 바꾸었을때 내림차순이 깨지지 않는다는것만 알 수 있으면 단순히 뒤집으면 오름차순이 됨을 알 수 있다.

귀류법으로 바꿨을때 깨진다고 생각해보자. 그러니까 \(A[K] \ge A[H+t]\)(이때 \(0 \le t \le n-1-t\)) 가 성립할 수 있어야 하는데, 이는 \(A[K] \le A[H]\) 이고, \(A[H] \ge A[H+t]\)(단 \(0 \le t \le n-1-t\))이기에, 말이 되지 않음을 알 수 있다.

이제 실제 구현을 살펴보도록 하자.

next_permutation의 가능한 구현체 코드

bool next_permutation(BidirIt first, BidirIt last){
// 수열의 last는 마지막 다음의 존재하지 않는 원소인데, first와 last 가 같다는 것은 잘못된 입력이다.
if(first == last) return false;
 BirdIt i = last;
//시작과 끝이 같다는 것은 한칸짜리 수열이고, 이거는 다음 순열이 있을 수 없다.
if(first == --i) return false;

 while(true){
 	BidirIt i1, i2;

  i1 = i
  if(*--i < *i1){//--i는 이전것 i1는 현재의 것을 의미한다. 즉 A[k] < A[k+1] 인지를 테스트 하는 것이다.
  	i2 = last;
   while(!(*i < *--i2));//끝에서부터 A[K] < A[h]를 만족하는 h를 찾는 과정
   std::iter_swap(i,i2); // A[k]와 A[h]를 바꾸는 작업
   std::reverse(i1,last);// 내림차순을 정렬된 부분 수열을 오름차순으로 만들어준다.
   return true;
  }
  if(i == first) {//완전 내림차순이다.
  	std::reverse(first,last);//뒤집고
   return false;//더이상 없음을 알려준다
  }
 }
}

PS를 할 때, 유용하게 쓰이는 함수인 next_permutation의 구현은 생각보다 복잡하지 않았다.

참고한 글

http://www.cplusplus.com/reference/algorithm/next_permutation/