1. 概述
在组合数学中，K 组合问题指的是：从一个包含 n 个元素的集合中，选出所有包含 k 个元素的子集（不考虑顺序）。这类子集的数量由二项式系数决定：
$$ \binom{n}{k} = \frac{n!}{k!(n-k)!} $$
虽然计算数量本身很简单，但要枚举所有这些子集却相对复杂。本文将介绍几种经典的生成算法，包括：
- 字典序生成（Lexicographic Generation）
- 背包生成（Filling a Rucksack Generation）
- 旋转门生成（Revolving Door Generation）
- 准完美方案（Near-Perfect Schemes）
- 完美方案（Perfect Schemes）
这些算法最早由计算机科学家 Donald Knuth 在《计算机程序设计艺术》（The Art of Computer Programming）中系统总结。
2. 字典序生成法
字典序生成法是一种直观且常用的生成方式。它将所有 k 组合按升序排列，便于查找和遍历。
核心思想
假设集合为 {0, 1, ..., n-1}，我们以降序排列组合元素，例如 [2, 1, 0] 表示组合 {0, 1, 2}。
算法模拟了多层嵌套循环的逻辑。例如，k = 3 时，等价于以下 Java 伪代码：
for (int c3 = 2; c3 < n; c3++) {
for (int c2 = 1; c2 < c3; c2++) {
for (int c1 = 0; c1 < c2; c1++) {
visit(c3, c2, c1);
}
}
}
每次迭代中，我们找到最右边可以递增的元素 cj，然后将它后面的元素设置为最小值。
示例
当 n = 6，k = 3 时，生成顺序为：
210
420
510
532
310
421
520
540
320
430
521
541
321
431
530
542
410
432
531
543
3. 背包生成法
3.1 二项树（Binomial Trees）
该方法将组合问题建模为背包问题，并利用二项树（Binomial Trees）进行递归构造。
二项树 Tₙ 的定义如下：
- T₀ 是一个单节点
- Tₙ 由一个根节点和 n 个子树 Tₙ₋₁, ..., T₀ 组成
例如，T₄ 的结构如下：
Tₙ 中第 k 层的节点数等于 C(n, k)，因此组合生成可以看作是 Tₙ 的第 k 层节点遍历。
3.2 背包算法实现
我们可以使用前序遍历的方式访问所有有效节点。核心逻辑是：
- 初始时选择 k 个元素
- 然后尝试在不超出容量的前提下添加新元素
- 若当前元素不再可用，回溯并尝试下一个可能的组合
4. 旋转门生成法
4.1 Gray 码简介
Gray 码是一种二进制编码方式，相邻两个编码只有一位不同。我们可以利用 Gray 码生成 k 组合，使得每次只变化一个元素。
4.2 旋转门算法实现
我们用一个长度为 n 的比特串表示当前组合：1 表示选中，0 表示未选中。每次只翻转两个比特（一个 1 和一个 0），模拟“旋转门”切换。
生成逻辑如下：
- 从全 0 开始
- 每次只交换一个 1 和一个 0
- 确保始终有 k 个 1
例如，n=6, k=3 时，生成的 Gray 码序列如下：
000111
011010
110001
101010
001101
011100
110010
101100
001110
010101
110100
100101
001011
010110
111000
100110
011001
010011
101001
100011
转换为组合后为：
210
431
540
531
320
432
541
532
321
420
542
520
310
421
543
521
430
410
530
510
可以看到，每个组合中元素交替递增递减。
5. 准完美与完美方案
5.1 准完美方案（Near-Perfect Schemes）
如果每次只改变一个组合元素（即只改变一个 cⱼ），我们称之为齐次序列（homogeneous sequence）。
旋转门算法并不满足这个条件，比如从 210 到 320 就改变了两个元素。
我们可以构造齐次序列，例如：
210 → 420 → 532 → 510 → 310 → 410 → ...
这种序列被称为 Chase 序列，是准完美方案的一种。
5.2 完美方案（Perfect Schemes）
如果每次只交换相邻两个比特（即只移动一个元素的位置），我们称之为完美方案。
数学家已经证明，完美方案只在以下情况存在：
- k ≤ 1
- n - k ≤ 1
- k × (n - k) 为奇数
也就是说，完美方案只在 4 分之一的情况下存在。
6. 算法对比
下图展示了不同算法生成组合时的二进制输出热图，清晰地体现了各种方法的规律性：
7. 总结
本文介绍了五种经典的 K 组合生成算法：
| 算法名称 | 特点 | 是否齐次 | 是否完美 |
|---|---|---|---|
| 字典序生成 | 简单直观，易于实现 | ❌ | ❌ |
| 背包生成 | 利用二项树结构 | ❌ | ❌ |
| 旋转门生成 | 使用 Gray 码，相邻只变一位 | ❌ | ❌ |
| 准完美方案 | 每次只变一个元素，变化范围 ≤ 2 | ✅ | ❌ |
| 完美方案 | 每次只交换相邻元素 | ✅ | ✅（仅在特定条件下） |
这些算法各有优劣，选择时应根据具体需求权衡性能与实现复杂度。