<next_permutation> 모든 경우의 수 정렬

벡터를 정렬할 때 정렬 될 수 있는 모든 경우의 수를 물어보는 문제가 있다. 이러한 경우 해당 함수를 사용한다. 

 

즉, A B C 를 정렬하고 싶은데 모든 경우를 정렬하면,

 

ABC
ACB
BAC
BCA
CAB
CBA

 

순으로 정렬이 된다. 해당 함수는 do{} while() 과 많이 쓰인다. 

 

이때 주의할 점은 do while을 사용하기 전에 저장되어있던 순 부터 사전순으로 정렬된다

 

다시 말해, BCA 에서 permutation 을 수행한다면 ABC부터 정렬되는게 아니라 BCA에서부터 CBA까지 정렬된다는

점이다. 

 

해당 함수를 이해하고 문법을 공부하자

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

using namespace std;

int main() {
    int answer = 0;
    vector <char> v1 = { 'A','B','C' }; 
    vector <char> v2 = { 'B','C','A' };
    vector <int> v3 =  { 1,2,3 }; 
    vector <char> v4 = { 'B','C','A' };
    do {
        for (auto x : v1)cout << x; 
        cout << "\n"; 
    } while (next_permutation(v1.begin(), v1.end()));//계속해서 정렬
    cout << "\n"; 

    do {
        for (auto x : v2)cout << x;
        cout << "\n";
    } while (next_permutation(v2.begin(), v2.end()));//계속해서 정렬
    cout << "\n";

    do {
        for (auto x : v3)cout << x;
        cout << "\n";
    } while (next_permutation(v3.begin(), v3.end()));//계속해서 정렬

    do {
        for (auto x : v4)cout << x;
        cout << "\n";
    } while (prev_permutation(v4.begin(), v4.end()));//계속해서 정렬
    cout << "\n";
}

* next_permutation의 반대는 prev_permutation