[c++/알고리즘] next_permutation (순열)

c++에는 변수 n의 순열을 구할 수 있는 함수가 있다. 

 

순열이란?
서로 다른 n개의 원소에서 r개를 뽑아 한 줄로 세우는 경우의 수이다. 

순열의 갯수는 n!이다. 

 

예를들어, 배열이 {1,2,3} 이라면 

순열은 {1,2,3} {1,3,2} {2,3,1} {2,1,3} {3,1,2} {3,2,1} 이다. 

 

기본 문법은 다음과 같다. 

// default
bool next_permutation (BidirectionalIterator first, BidirectionalIterator last);

// custom
bool next_permutation (BidirectionalIterator first, BidirectionalIterator last, Compare comp);

next_permutation은 순열을 구할 배열의 시작과 끝 iterator를 인자로 받는다. 만약 해당 컨테이너에 다음 순열이 존재하면 그 컨테이너의 원소를 해당 순열 순서로 바꾸고 true를 반환하고, 다음 순열이 없다면 false를 반환한다.

 

사용할 때 주의할 점이 있다면

1. 이를 사용하기 위해서는 오름차순으로 정렬을 해야한다. 

2. 중복이 있는 원소는 중복을 제외하고 순열을 만들어준다. 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main() {
    vector<int> v{ 1, 2, 3};
 
    sort(v.begin(), v.end());
 
    do {
        for (auto it = v.begin(); it != v.end(); ++it)
            cout << *it << ' ';
        cout << endl;
    } while (next_permutation(v.begin(), v.end()));
}