[C++] [Algorithm] C++에서 next_permutation 함수( prev_permutation 함수)를 통해서 순열 구하기

next_permutation => 직역하자면, 다음 수열이라는 의미입니다.

STL에서 제공하는 함수이며 vector, 배열로 구현이 가능합니다.

// 사전 순으로 정렬

1 3 4 2 의 다음 수열은 1 4 2 3 이 됩니다.

이때 1 4 2 3 을 만들기 위해서 4가지 단계를 거치는데

1. 어디까지가 감소 수열인가 찾기.

1 3 4 2 (감소 수열 4 2) 

이떄 i = 2

2. i-1보다 작거나 같으며, 가장 뒤에 있는 수 j 를 찾기

1 3 4 2 (2보다 작으며, 가장 앞에 있는 수를 찾습니다)

이때 j = 3 (2를 가르킵니다)의 이전 인덱스 j = 2( 4를 가르킵니다)

3.  그 둘을 Swap 시킵니다.

1 4 3 2

4.  i -1 이후로 뒤집습니다.

1 4 2 3

#include<iostream>
#include<vector>
 
using namespace std;
 
bool next_permutation(int *a, int n){
    int i = n-1;                    // 뒤부터 시작 
    while(i > 0 && a[i] <= a[i-1])  // 어디까지가 감소수열인가?? 
        i -= 1;
    if(i <= 0)                    // 전체가 감소수열이다. 
        return false;                // 다음 수열은 존재하지 않는다.
    int j = n-1;
    while(a[i-1] >= a[j])                
        j -= 1;            
    swap(a[i-1],a[j]);                // 찾은 수의 바로 앞 swap i-1 
    j = n - 1;                        // j는 마지막 
    while(i < j){                    // i-1 이후로, swap해줌 
        swap(a[i],a[j]);
        i +=1;
        j -=1;
    }
    return true;
}
 
int main(){
    int n;
    cin >> n;
    
    int *v = new int[n];
        
    for(int i = 0; i < n; i++)
        v[i] = i+1;
        
    do{                               
        for(int i = 0; i < n; i++)
            cout << v[i] << ' ';
        cout << '\n';
    }while(next_permutation(v,n));
    
    return 0;
}

C++의 STL에서 제공하는 함수도 존재합니다.

간단하게 사용하면 됩니다.

#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int main(){
    vector<int> a;
    int n;
    cin >> n;
    
    for(int i = 0; i < n; i++){
        int tmp;
        cin >> tmp;
        a.push_back(tmp);
    }
    
    do{
        for(int i = 0; i < n; i++)
            cout << a[i];
        cout << '\n';        
    }while(next_permutation(a.begin(), a.end()));
    
    return 0;
}

※ 본 글은 개인 포트폴리오 혹은 공부용으로 사용하기 때문에, 무단 복사 유포는 금지하지만, 개인 공부 용도로는 얼마든지 사용하셔도 좋습니다.