[C++ / Algorithm] 순열(next_permutation) 사용 방법과 조합(Combination) 구하기

 

순열을 구하는 next_permutation 함수

 

순열

 

수학적으로 순열(permutation)이란 서로 다른 n개의 원소에서 r개를 뽑아 한 줄로 세우는 경우의 수를 말합니다. 원소를 한 줄로 세우기 때문에 원소의 조합이 같더라도 순서가 다르면 다른 방법으로 봅니다. 

 

예를 들어 집합 {1, 2, 3}의 원소들의 모든 순열을 구한다면

{1, 2, 3}

{1, 3, 2}

{2, 1, 3}

{2, 3, 1}

{3, 1, 2}

{3, 2, 1}

로 총 6가지가 나오게 됩니다. 

 

 

 

 

next_permutation

 

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

 

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

 

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)을 구할 수 있습니다. 

 

 

 

 

next_permutation 사용예시 - {1, 2, 3}의 모든 순열 출력하기

#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()));
}

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

 

 

 

 

 

순열을 이용한 조합(Combination) 구하기

 

조합(Combination)이란 n개의 원소 중에서 r개를 뽑는 경우의 수를 말합니다. 순열은 순서가 중요했지만, 조합은 원소 r개를 뽑기만 하면 되기 때문에 순서는 중요하지 않습니다. 

 

 

 

조합(Combination) 구하기

 

배열 s의 n개의 원소 중에서 r개의 원소를 택하는 방법은 다음과 같습니다. 

 

1. 우선 크기가 n인 배열 temp를 만들어 r개의 원소는 1로, (n-r)개의 원소는 0으로 초기화합니다. 
2. temp의 모든 순열을 구합니다. 
3. temp의 순열에서 원소값이 1인 인덱스만 배열 s에서 가져옵니다. 

temp에서 1이 있는 자리의 원소는 포함하고 0이 있는 자리의 원소는 미포함한다고 생각하면 쉽습니다. 이때 next_permutaion을 사용하면 오름차순으로 정렬되기 때문에, 조합은 내림차순으로 출력됩니다. 하지만 prev_permutation을 쓰면 모든 조합의 경우의 수를 오름차순으로 출력 가능합니다. 

 

※ prev_permutation은 내림차순 정렬된 데이터를 받아서 이전 순열로 바꿔줍니다. 

 

 

 

 

사용 예시 - {1, 2, 3, 4} 중 2개의 원소를 고르는 모든 경우의 수 출력하기

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main() {
    vector<int> s{ 1, 2, 3, 4 };
    vector<int> temp{ 1, 1, 0, 0 };
 
    do {
        for (int i = 0; i < s.size(); ++i) {
            if (temp[i] == 1)
                cout << s[i] << ' ';
        }
        cout << endl;
    } while (prev_permutation(temp.begin(), temp.end()));
}

 

1 2
1 3
1 4
2 3
2 4
3 4

 

 

 

 

 

 

 

 

참고 사이트 : http://www.cplusplus.com/reference/algorithm/

https://twpower.github.io/90-combination-by-using-next_permutation

 

 

 

공부한 것을 정리한 내용입니다. 수정할 부분이 있다면 알려주시면 감사하겠습니다 :)