[Algorithm][Template] 순열과 조합

C++에서는 순열과 조합을 각각 next_permutation, prev_permutation을 이용해 쉽게 구할 수 있다.

next_permutation

C++의 algorithm 헤더에는 n개의 원소의 순열을 구할 수 있는 next_permutation이라는 함수가 있습니다. 기본적 문법은 다음과 같습니다. 

 

1 2 3 4 5 6 7

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

cs

 

next_permutation은 순열을 구할 컨테이너(쉽게 말해 배열)의 시작과 끝 iterator를 인자로 받습니다. 만약 해당 컨테이너에 다음 순열이 존재하면 그 컨테이너의 원소를 해당 순열 순서로 바꾸고 true를 반환하고, 다음 순열이 없다면 false를 반환합니다. 위 코드의 custom에서 볼 수 있듯이 비교 함수 comp를 인자로 넘기는 것도 가능합니다. 

 

 

 

next_permutation을 사용할 때는 몇 가지 주의할 점이 있습니다. 

1. 오름차순으로 정렬된 값을 가진 컨테이너로만 사용가능합니다.
2. default로 operator < 를 사용해 순열을 생성합니다. 즉 오름차순으로 순열을 생성합니다. 
3. 중복이 있는 원소들은 중복을 제외하고 순열을 만들어줍니다. 

3번의 예시를 들자면 {0, 0, 1}과 같은 배열의 순열을 구한다면 중복을 제외한

{0, 0, 1}, {0, 1, 0}, {1, 0, 0}이 됩니다. 이를 이용해 조합(Combination)을 구할 수 있습니다. 

출처: https://mjmjmj98.tistory.com/38 [Live passionate😎]

 

<순열 - 중복 포함하지 않음> 

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

using namespace std;

vector<int> v{2, 1, 3};

int main(void) {

    // 1. next_permutation 사용을 위한 v 오름차순 정렬
    sort(v.begin(), v.end());

    // 2. 오름차순으로 정렬된 순열 출력
    do {
        for (auto it = v.begin(); it != v.end(); it++) {
            cout << *it << " ";
        }
        cout << endl;
    }
    while (next_permutation(v.begin(), v.end()));

    return 0 ;
}

<조합 - 중복 포함하지 않음>

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

using namespace std;

vector<int> v{2, 1, 3};
vector<int> t{1, 1, 0};

int main(void) {

    // 1. prev_permutation 사용을 위한 t 내림차순 정렬
    sort(t.begin(), t.end(), greater<int>());

    // 2. 내림차순으로 정렬된 데이터를 받아서 순열로 뽑고 그 부분만 v에서 뽑아내 조합으로 만들기
    do {
        for (int i = 0; i < v.size(); i++) {
            if (t[i]) {
                cout << v[i] << " ";
            }
        }
        cout << endl;
    }
    while (prev_permutation(t.begin(), t.end()));

    return 0 ;
}

do-while은 쓰면 안 좋다지만, 위의 경우는 예외로 쓰도록 하자.

참고로, next_permutation, prev_permutation 함수는 터미널에서는 기본 제공되지만, 백준과 같은 사이트에서 사용하려면

#include <algorithm>을 해줘야 한다.

 

시간복잡도

 - next_permutation 자체가 O(n)이고 nPr 자체는 O(n!) 이므로 위 템플릿처럼 순열 조합을 구현하면 O(n*n!)이 된다.