引言

如果你可以创建一组无需逗号或分隔符就能唯一解码的代码，这会对 DNA 测序、数据压缩和错误校正产生什么影响？

这不是纯粹的学术好奇——commafree codes 在这些领域都有实际应用。在我上一篇文章中，我们探讨了指数级复杂度的递归算法。今天，我们将深入 Knuth 的 Algorithm C，它通过巧妙的回溯和稀疏数据结构实现了惊人的效率。

本文你将学到：

• Algorithm C 如何将复杂度从 O(2^n) 降低到可管理的水平
• 用于剪枝搜索空间的 ingenious “poison array” 技术
• 实用的实现技巧和性能优化方法

无论你是正在研读 TAOCP 4B，还是单纯热爱优雅算法，这篇深度解析都将改变你对组合搜索的思考方式。

Algorithm C

框架

算法框架分为五步：

1. 初始化数组
2. 选择主串
3. 更新选择的影响
4. 递归尝试并打印结果
5. 回溯

初始化

这一步之所以单独提出来，是因为除了上一篇介绍的数据结构外，还有不下 10 个数组需要初始化。它们的主要作用是：

• 记录颜色和候选集
• 记录递归信息以便回溯

我尝试用伪代码来描述，但发现太冗长了，而且 x, c 这些字母看得头疼。这里我们只关注 MEM 数组。

MEM 数组初始化示例

回到上篇最后的例子：

这是当 m=2 时，我们需要初始化的 MEM 数组。它恰好每行 16 个，存下了所有 4 位二进制。

第一行记录的是每个 code 的颜色：

• #0000 #0100 #1000 #1010 #1111 已经是红色
• 其中 3 个是红色好理解，因为它们属于 abab 形式，本身就被排除在外

问题来了：为什么 #0100 和 #1000 也被涂成红色呢？

先自己尝试解释，我在文末揭晓答案。

剩下的辅助数组和变量就不展开了，直接进入下一步。

尝试主串

接下来我们大胆地从候选集中选一个颜色是蓝色的码，选中之后将它变成绿色，假如这次我们选择 #0010，同时记录下这一步的选择，进入下一步。

更新&标记

1. 更新稀疏集合

当我们选了 #0010 后，根据 7 个稀疏集合的定义，我们要可以快速更新它们，从而继续更新状态数组的颜色。

P 集合的处理：

• 只要把 #0010 相应的前缀链表”关闭”即可
• 比如 P1 在 MEM[20-24] 之间记录的是 \(0\star \star \star\) 开头的码
• 只要令 MEM[30] 是链表头-1 就行了，也就是 MEM[30]=1f
• P2 同理，”关闭” \(00\star \star\)
• S 集合也是如此处理

CL 集合的处理：

• CL 集合记录蓝色词的循环移位集合
• 选了 #0010 后，要把它所在的位移集合都移除掉
• 也就是 MEM[140-141] 代表的集合，将 MEM[150]=13f

更新前后对比：

更新前：

更新后：

状态标记

你也许注意到在更新后的 CL 集合中，还少了 #1001，这又是为什么呢？ 这里要引出又一个数组 poison，当我们选择了 #0010 后，我们将

\(\)(\star001, 0\star \star \star), (\star \star00,10\star \star), (\star \star \star 0,010\star)\(\)

放入 poison 数组，对于第一组，因为 \(0\star \star \star\) 包含了绿色的 #0010，那么 \(\star001\) 必然为红，也就可以把 #1001 变成红，也就解释了为什么上面 CL 也删掉 #1001（另外 6 个集合也要对应删掉 #1001）。换句话说，每一对前缀和后缀必须至少包含一绿一红，同理，第三组因为 \(\star \star \star0\) 已经包含绿了，那\(010\star\) 都必须是红。对于第二组因为包含全为蓝，无法删除，就先保留。

回溯

当我们走到了尽头发现没有蓝色状态的码时，我们就要开始回溯了，鉴于精妙的数据结构，我们只要完成 更新&标记 的逆操作就好，对于 poison 数组的记录，我们只要把上面单独删除的码加回到各个集合就好，这里特别提一下，因为稀疏集合在删除时只是把待删元素交换到末位没有物理删除，所以添加回来只要简单改一下 TAIL 指针就好。然后对于这次选中的候选码，简单地“打开”集合就好，也是修改 TAIL 指针。

小结

核心要点回顾

虽然搜索算法不可避免地具有指数级复杂度，但通过巧妙的数据结构和搜索策略，我们仍然可以显著提高效率。

关键优化技术：

1. 稀疏集合：快速更新和回溯
2. Poison 数组：智能剪枝搜索空间
3. 颜色标记：高效状态管理

遗留问题解答

为什么 #0001 和 #0010 在初始化时就是红色？

因为题目定义解法必须包括 #0001 或者 #0010 其中一个。不管选哪个，#0100 和 #1000 都和 #0001 或者 #0010 属于同一个主码，所以被排除。

课后题与思考

最复杂的莫过于书中列出的表格。如果你恰好有书，可以看到关于算法 C 的表格 1 和表格 2，它们分别展示了算法 C 的第 1 步和第 2 步。但实际操作起来，我发现了一些有趣的地方。留下几道问题帮助读者更好理解 MEM 的奥妙所在。

挑战题目

1. 排序之谜：在表格 1 中，可以看到 20 这行分成了两部分，每部分 5 个数。为什么前半部分记录了 #0001 #0010 #0011 是递增的，后半部分第一个却是 #1100 而不是 #1001 呢？

2. 地址解析：接上题，你的答案能解释 MEM[5d] 和 MEM[5e] 吗？MEM[bc] 和 MEM[bd] 呢？

3. 赋值顺序：在表格 1 中，最后 3 行 cl 数组的赋值顺序是什么？为什么 MEM[146] 是 #1100 而 MEM[147] 是 #1001 排在后面呢？

4. 初始化逻辑：为什么初始化首先排除了 #0100 和 #1000？（有没有好好听讲 😉）

延伸学习资源

进阶阅读

• TAOCP 4B：算法 C 的原始描述（注意地址 40d 应为 4d 的笔误）
• Knuth 的论文：关于稀疏集合的优化技巧
• 组合算法：回溯算法的理论基础

实践项目

1. 实现完整的 Algorithm C（从 m=2 开始）
2. 可视化算法的搜索过程
3. 比较不同剪枝策略的效果

后记

其实这 3 篇文章只是对 Knuth 的 TAOCP 4B 中 algorithm C 的粗浅解读。虽然书里列出了算法的 12345 步，但我并不认为用序号的形式展示一段带分支的代码是个好主意。直接用伪码反而更加清晰，所以我在叙述时完全抛开了书中繁琐的步骤，而是从更符合代码直觉的角度介绍了算法的实现。

有趣发现

PS：在 Ex41 和算法 C 的实现中，Knuth 偶尔会把 MEM 的地址写成 40d，而应该是 4d。不幸的是，这种错误已经被人指出来了。如果想拿到 Knuth 签名的 San Serriffe 银行支票，还是要趁早哦！