combination.md
조합
조합이란 n 개의 원소 중에서 r 개를 순서에 관계없이 뽑는 것이다. 위 공식은 그렇게 뽑는 경우의 수를 의미한다. {1, 2, 3} 배열에서 2개의 숫자를 조합으로 뽑는다고 하면 아래와 같다.
- 1 2
- 1 3
- 2 3
순열은 1 2 와 2 1 을 다른 것으로 세지만, 조합은 같은 것으로 센다.
3개의 숫자를 조합으로 뽑으면 아래와 같이 1개만 나온다.
- 1 2 3
(3 - 3)! 은 0! 이고, 0! 은 1 로 정의된다. 따라서 3! / (3! × 1) = 1 이다.
구현
조합은 중첩 for 문 또는 재귀함수로 구현한다. 중첩 for 문은 뽑는 개수만큼 for 문을 겹쳐 써야 하므로, 뽑는 개수가 적을 때 주로 쓴다. 뽑는 개수가 많거나 실행 중에 정해지면 재귀함수를 쓴다.
위 그림은 {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