모든 $K$-조합 생성하기¶
이 글에서는 모든 $K$-조합을 생성하는 문제를 다룹니다. 자연수 $N$과 $K$가 주어지고, $1$부터 $N$까지의 수로 이루어진 집합을 생각합니다. 목표는 크기가 $K$인 부분집합을 모두 구하는 것입니다.
사전순으로 다음 $K$-조합 생성하기¶
먼저 조합들을 사전순으로 생성해 보겠습니다. 이를 위한 알고리즘은 간단합니다. 첫 번째 조합은 ${1, 2, ..., K}$입니다. 이제 사전순으로 이 조합 바로 다음에 오는 조합을 찾는 방법을 살펴봅시다. 이를 위해 현재 조합에서 아직 가능한 최댓값에 도달하지 않은 원소 중 가장 오른쪽에 있는 원소를 찾습니다. 이 원소를 찾으면 그 값을 $1$만큼 증가시키고, 그 뒤에 오는 모든 원소에는 가능한 가장 작은 값을 할당합니다.
bool next_combination(vector<int>& a, int n) {
int k = (int)a.size();
for (int i = k - 1; i >= 0; i--) {
if (a[i] < n - k + i + 1) {
a[i]++;
for (int j = i + 1; j < k; j++)
a[j] = a[j - 1] + 1;
return true;
}
}
return false;
}
인접한 조합끼리 원소 하나만 다르도록 모든 $K$-조합 생성하기¶
이번에는 인접한 조합끼리 정확히 원소 하나만 다르도록 하는 순서로 모든 $K$-조합을 생성하려고 합니다.
이 문제는 그레이 코드를 사용하여 해결할 수 있습니다: 각 부분집합에 비트마스크를 대응시키면, 그레이 코드로 이 비트마스크들을 생성하고 순회하여 답을 얻을 수 있습니다.
$K$-조합을 생성하는 문제는 그레이 코드를 이용한 다른 방법으로도 해결할 수 있습니다: $0$부터 $2^N - 1$까지의 수에 대한 그레이 코드를 생성하고, $1$을 $K$개 포함하는 코드만 남깁니다. 놀라운 사실은 이렇게 얻은, 켜진 비트가 $K$개인 마스크들의 수열에서 임의의 인접한 두 마스크(첫 번째 마스크와 마지막 마스크도 순환적인 의미에서 인접한 것으로 봅니다)가 정확히 두 비트만 다르다는 것이며, 이것이 바로 우리의 목표(수 하나를 제거하고 수 하나를 추가하는 것)입니다.
이를 증명해 봅시다:
증명을 위해 수열 $G(N)$($N$번째 그레이 코드를 나타냅니다)을 다음과 같이 얻을 수 있다는 사실을 상기합니다:
즉, $N-1$에 대한 그레이 코드 수열을 생각하고 모든 항 앞에 $0$을 붙입니다. 그리고 $N-1$에 대한 그레이 코드 수열을 뒤집은 것을 생각하여 모든 마스크 앞에 $1$을 붙인 뒤, 이 두 수열을 이어 붙입니다.
이제 증명을 할 수 있습니다.
먼저 첫 번째 마스크와 마지막 마스크가 정확히 두 비트만 다르다는 것을 증명합니다. 이를 위해서는 수열 $G(N)$의 첫 번째 마스크가 $N-K$개의 $0$ 뒤에 $K$개의 $1$이 오는 형태라는 점에 주목하는 것으로 충분합니다. 첫 번째 비트가 $0$이고 그 뒤에 $(N-K-1)$개의 $0$이 오며, 그 뒤에 $K$개의 켜진 비트가 오고, 마지막 마스크는 $1$ 다음에 $(N-K)$개의 $0$, 그다음에 $K-1$개의 $1$이 오는 형태가 됩니다. 수학적 귀납법을 적용하고 $G(N)$에 대한 공식을 사용하면 증명이 완료됩니다.
이제 우리가 할 일은 인접한 두 코드도 정확히 두 비트가 다르다는 것을 보이는 것이며, 이는 그레이 코드 생성을 위한 재귀 방정식을 살펴봄으로써 할 수 있습니다. $G(N-1)$로 만들어진 두 절반 각각에 대해서는 이 명제가 참이라고 가정합시다. 이제 (두 절반을 이어 붙여) 경계에서 새로 만들어지는 연속된 쌍 역시 유효하다는 것, 즉 정확히 두 비트만 다르다는 것을 증명해야 합니다.
첫 번째 절반의 마지막 마스크와 두 번째 절반의 첫 번째 마스크를 알고 있으므로 이는 가능합니다. 첫 번째 절반의 마지막 마스크는 $1$ 다음에 $(N-K-1)$개의 $0$이 오고, 그 다음에 $K-1$개의 $1$이 오는 형태입니다. 그리고 두 번째 절반의 첫 번째 마스크는 $0$ 다음에 $(N-K-2)$개의 $0$이 이어지고, 그 다음에 $K$개의 $1$이 오는 형태입니다. 따라서 두 마스크를 비교하면 서로 다른 비트가 정확히 두 개임을 알 수 있습니다.
다음은 가능한 $2^{n}$개의 부분집합을 모두 생성하고 그중 크기가 $K$인 부분집합을 찾는 방식으로 동작하는 단순한 구현입니다.
int gray_code (int n) {
return n ^ (n >> 1);
}
int count_bits (int n) {
int res = 0;
for (; n; n >>= 1)
res += n & 1;
return res;
}
void all_combinations (int n, int k) {
for (int i = 0; i < (1 << n); i++) {
int cur = gray_code (i);
if (count_bits(cur) == k) {
for (int j = 0; j < n; j++) {
if (cur & (1 << j))
cout << j + 1;
}
cout << "\n";
}
}
}
유효한 조합만을 만들어 내어 $O\left(N \cdot \binom{N}{K}\right)$에 동작하는 더 효율적인 구현도 존재한다는 점을 언급할 만합니다. 다만 이 구현은 본질적으로 재귀적이며, $N$이 작은 경우에는 앞의 풀이보다 상수가 더 클 가능성이 높습니다.
이 구현은 다음 공식으로부터 유도됩니다:
이 공식은 그레이 코드를 구하는 일반 방정식을 변형하여 얻은 것으로, 적절한 원소들로부터 부분 수열을 선택하는 방식으로 동작합니다.
구현은 다음과 같습니다:
vector<int> ans;
void gen(int n, int k, int idx, bool rev) {
if (k > n || k < 0)
return;
if (!n) {
for (int i = 0; i < idx; ++i) {
if (ans[i])
cout << i + 1;
}
cout << "\n";
return;
}
ans[idx] = rev;
gen(n - 1, k - rev, idx + 1, false);
ans[idx] = !rev;
gen(n - 1, k - !rev, idx + 1, true);
}
void all_combinations(int n, int k) {
ans.resize(n);
gen(n, k, 0, false);
}