🤮

[cpp] 조합(Combination) 구현


조합 구현하기

보통 조합을 구현한다고 하면 아래 함수를 볼 수 있다.

1int combination(int n, int r)
2{
3 if(n == r || r == 0)
4 return 1;
5 else
6 return combination(n - 1, r - 1) + combination(n - 1, r);
7}

조합의 수학 공식 nCr=n1Cr1+n1Cr{_{n} C_r}= {_{n-1} C_{r-1}} + {_{n-1} C_r}을 그대로 구현한 것이다.

이렇게 구현하면 조합의 수는 쉽게 구할 수 있지만, 실제 조합들의 경우의 수를 눈으로 볼 수는 없다. 물론 이 함수를 응용해서 실제 조합들을 얻을 수 있게 바꿀 수는 있겠지만, 더 쉬운 방법이 있다.

바로 STL의 'algorithm'에서 제공되는 next_permutation 함수를 사용하는 방법이다.

next_permutation

next_permutation은 이름에서 알 수 있듯이 순열(permutation)을 구해준다. 요놈은 현재 나와있는 수열에서 인자로 넘어간 범위에 해당하는 다음 순열을 구하고 true를 반환한다. 다음 순열이 없다면 false를 반환한다. next_permutation은 인자로 반복자를 받기 때문에 vector 뿐만 아니라 string 타입의 변수도 순열을 구할 수 있다.

1int main() {
2 // 1부터 4까지 벡터에 저장
3 vector<int> v(4);
4 for(int i=0; i<4; i++){
5 v[i] = i+1;
6 }
7 // next_permutation을 통해서 다음 순열 구하기
8 do{
9 for(int i=0; i<4; i++){
10 cout << v[i] << " ";
11 }
12 cout << '\n';
13 } while(next_permutation(v.begin(),v.end()));
14}
15// 1 2 3 4
16// 1 2 4 3
17// ...
18// 4 3 1 2
19// 4 3 2 1

이 함수를 응용해서 조합을 구할 수 있다.

nCk를 구하고 싶다면, n 개의 벡터 원소에 1을 k개 그래고 나머지를 0으로 해서 순열을 돌리고 1에 해당하는 원소만 들고오면 된다.

1vector<int> num(N), perm(N);
2for (int i = 0; i < N; i++) {
3 num[i] = i + 1;
4}
5for (int i = N - k; i < N; i++) {
6 perm[i] = 1;
7}
8do {
9 for(int i = 0; i < perm.size(); i++){
10 if (perm[i] == 1){
11 printf("%d ", num[i]);
12 }
13 }
14
15 printf("\n");
16} while(next_permutation(perm.begin(), perm.end()));

참조:
https://twpower.github.io/82-next_permutation-and-prev_permutation