combination.md

조합


nCr=(nr)=n!r!(n−r)! ^nC_r = \binom{n}{r} = \frac{n!}{r!(n-r)!}

조합이란 n 개의 원소 중에서 r 개를 순서에 관계없이 뽑는 것이다. 위 공식은 그렇게 뽑는 경우의 수를 의미한다. {1, 2, 3} 배열에서 2개의 숫자를 조합으로 뽑는다고 하면 아래와 같다.

순열은 1 2 와 2 1 을 다른 것으로 세지만, 조합은 같은 것으로 센다.

3개의 숫자를 조합으로 뽑으면 아래와 같이 1개만 나온다.


3C3=(33)=3!3!(3−3)!=1 ^3C_3 = \binom{3}{3} = \frac{3!}{3!(3-3)!} = 1

(3 - 3)! 은 0! 이고, 0! 은 1 로 정의된다. 따라서 3! / (3! × 1) = 1 이다.


구현

조합은 중첩 for 문 또는 재귀함수로 구현한다. 중첩 for 문은 뽑는 개수만큼 for 문을 겹쳐 써야 하므로, 뽑는 개수가 적을 때 주로 쓴다. 뽑는 개수가 많거나 실행 중에 정해지면 재귀함수를 쓴다.

image

위 그림은 {1, 2, 3, 4, 5} 에서 3개를 뽑는 10가지 경우이다. 파란 칸이 뽑은 원소이다. 아래 두 코드는 이 10가지를 출력한다.


중첩 for 문

5개 중 3개를 뽑는 조합을 출력하는 코드이다.

#include <iostream>
using namespace std;

int n = 5;
int a[5] = {1, 2, 3, 4, 5};

int main()
{
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            for (int k = j + 1; k < n; k++)
            {
                cout << a[i] << " " << a[j] << " " << a[k] << '\n';
            }
        }
    }
    return 0;
}

재귀함수

vec 에는 원소가 아니라 인덱스를 담고, 출력할 때 a[i] 로 원소를 꺼낸다.

#include <iostream>
#include <vector>

using namespace std;

int n = 5, k = 3, a[5] = {1, 2, 3, 4, 5};

void print(vector<int> vec)
{
    for (int i : vec)
        cout << a[i] << " ";
    cout << '\n';
}

void combination(int start, vector<int> vec)
{
    if ((int)vec.size() == k) // base case
    {
        print(vec);
        return;
    }
    for (int i = start + 1; i < n; i++)
    {
        vec.push_back(i);
        combination(i, vec);
        vec.pop_back(); // restore
    }
    return;
}

int main()
{
    vector<int> vec;
    combination(-1, vec);
    return 0;
}
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5