Next permutation, 다음 순열 구하기

어떤 순열이 주어져 있을 때 다음 순서의 순열을 구하는 알고리즘이다. 참고로 여기서 말하는 순서는 어떤 요소들로 순열을 만들고 이 순열들을 사전 순서대로 정리하듯 정렬하였을 때를 기준으로 한다.
예를 들어 어떤 1, 2, 3을 가지고 모든 순열을 만들고 이를 사전 순서대로 정리하면 아래와 같다.

123
132
213
231
312
321

우리가 하고자 하는 것은 어떤 순열이 주어졌을 때 다음 순열을 구하는 것이다. 예를 들어 231 이 주어졌을 경우 312를 반환하는 것이다.

Algorithm

어떤 순열을 arr라고 하자.

1. arr[i] < arr[i+1] 인 i 중 가장 큰 값을 구한다.
2. i보다 큰 j에 대해 arr[j] > arr[i] 인 j 중 가장 큰 j를 구한다.
3. swap(arr[i],arr[j]) : i 와 j 인덱스에 해당하는 요소 둘을 swap 한다.
4. reverse(arr[i+1],arr[arr.size()-1]) : i+1의 인덱스에 해당하는 요소부터 arr의 끝까지 요소들의 순서를 모두 뒤집는다.

아래 순열에 대해 위 과정을 수행해보자.

5912874

첫 번째, arr[i] < arr[i+1] 인 가장 큰 i를 구하자.

---i---
5912874

두 번째, i보다 큰 j에 대해 arr[j] > arr[i] 인 j 중 가장 큰 j를 구한다.

---i--j
5912874

세 번째, i와 j 인덱스에 해당하는 요소 둘을 swap 한다.

---i--j
5914872

네 번째, i+1 인덱스 요소부터 배열 끝까지 해당하는 요소들의 순서를 뒤집는다.

----vvv
---i--j
5914278

참고로 첫 번째 과정에서 조건을 만족하는 i가 존재하지 않을 수 있다. 이 경우는 배열이 완전히 역순으로 정렬되어있는 경우이다.

next_permutation in STL

c++의 STL에는 이미 구현이 되어있다. 배열이나 vector 혹은 BidirectionalIterator가 사용 가능한 모든 형태에서 사용 가능하다. 다음 값을 찾을 수 있는 경우 true를 반환하며 완전 역순으로 정렬되어있어 다음 순열을 구할 수 없는 경우엔 false를 반환한다.

아래는 순열 1234의 다음 순열과 그다음 순열을 지속해서 출력하는 코드와 결과이다.

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int main(void){
    vector<int> vec = {1,2,3,4};
    while(next_permutation(vec.begin(),vec.end())){
        cout<<vec[0]<<vec[1]<<vec[2]<<vec[3]<<endl;
    }
    return 0;
}

1243
1324
1342
1423
1432
2134
2143
2314
2341
2413
2431
3124
3142
3214
3241
3412
3421
4123
4132
4213
4231
4312
4321

Own Implementation

스스로 구현해보자. 아래 코드는 단순히 위 algorithm으로 기술된 과정들을 코드로 나타낸 것뿐이다. 한 가지 다른 것은, 첫 번째 과정에서 조건에 맞는 i를 찾지 못한 경우 입력 전체를 뒤집는다.

#include <vector>
#include <iostream>

using namespace std;

// Just swap
void swap(int* p1,int*p2){
    int tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}

void nextPermutation(vector<int>& vec){
    int size = vec.size();
    int idx0 = -1, idx1 = -1;
    for(int i=0;i<size-1;++i){
        if(vec[i]<vec[i+1]) idx0 = i;
    }

    // if NO NEXT permutation, return reversed.
    if(idx0<0){
        for(int i=0;i<size/2;++i){
            swap(&vec[i],&vec[size-i-1]);
        }
        return;
    }

    for(int j=size-1;idx0<j;--j){
        if(vec[j] > vec[idx0]){
            idx1 = j;
            break;
        }
    }

    swap(&vec[idx0],&vec[idx1]);
    for(int i=idx0+1,j=size-1;i<j;++i,--j){
        swap(&vec[i],&vec[j]);
    }
}

// driver code
int main(void){
    vector<int> vec = {5,9,1,2,8,7,4};
    for(int i=0;i<15;++i){
        for(int j=0;j<7;++j){
            cout << vec[j] << ' ';
        }
        nextPermutation(vec);
        cout<<endl;
    }
}

위 코드는 순열 5912874와 그 이후 연속으로 나오는 순열 14개를 출력하는 코드이다. 아래는 그 결과이다.

5 9 1 2 8 7 4 
5 9 1 4 2 7 8
5 9 1 4 2 8 7
5 9 1 4 7 2 8
5 9 1 4 7 8 2
5 9 1 4 8 2 7
5 9 1 4 8 7 2
5 9 1 7 2 4 8
5 9 1 7 2 8 4
5 9 1 7 4 2 8
5 9 1 7 4 8 2
5 9 1 7 8 2 4
5 9 1 7 8 4 2
5 9 1 8 2 4 7
5 9 1 8 2 7 4