commafree code初次见面——生成
引言
commafree code 是一种自同步定长编码，和 Huffman 编码那种变长压缩码完全不同。给定 m 个字母构成的长度为 n 的码字集合 D，若任意两个码字 \(x_1x_2x_3x_4\) 与 \(x_5x_6x_7x_8\) 相邻时，中间的偏移子串 \(x_2x_3x_4x_5\)、\(x_3x_4x_5x_6\)、\(x_4x_5x_6x_7\) 均不在 D 中，则称 D 为 commafree code（又称自同步块码）。这一性质保证接收方无需分隔符即可正确分段解码。
以 n=4 为例：”likethis”中 “like” 和 “this” 是码字，而中间的偏移串 “iket”、”keth”、”ethi” 均不是码字。另外，自身循环串（如 dodo、gaga）不能成为码字，因为两个相同码字相邻后中间的偏移子串就是自身。
利用链表回溯生成 Langford 对
引言
我发现在以前的回溯算法中，很少提到链表的使用，虽然 Dancing link 算法已经用的炉火纯青了，但介绍它属于是“跳级”了，咱们既然从零单排回溯算法，那还要从链表在回溯中的简单用法讲起，这就要提 Langford 对的生成了。
Langford 对是一个组合数学中的概念。给定一个正整数 ，Langford 对是将数字 1 到 n 的每个数字重复两次，并以一种特定的方式排列，使得两个相同的数字之间恰好间隔等于该数字的位置数。 例如，对于 n=4，一种可能的 Langford 对排列是 23421314。在这里，每个数字重复两次，且两个 1 之间间隔 1 个位置；两个 2 之间间隔 2 个位置；以此类推。
反方向的回溯——Walker算法
引言
如果你看懂了上一篇的回溯基本法，那这篇更是小菜一碟，我将尝试在 read more 之前讲明白它。
相比基本法每次尝试是从$D_l$依次取一个然后验证，如果为假则剪枝，否则即等待成立，Walker 则从另一个角度出发，每次从$S_l$取完最小元素$x_l$后，直接更新下次的 $S_{l+1}$，把不符合条件从集合中删掉，然后接着往下走直到$l>n$。回溯时则直接令$S_l\leftarrow S_l \backslash x_l$ 去除$x_l$，然后接着选下一个。
从零单排回溯算法 algorithm B
引言
当我要介绍 Knuth 在 23 年圣诞节时的演讲 Dancing cell 时，我发现我缺少了太多的上下文，算法虽然不难讲清楚，但为什么要这么做，这个算法有什么应用价值我并不清楚，视频中提到了这是从 Knuth 的经典著作《The Art of Computer Programming》(TAOCP)第 7 章开始的。出于好奇，我翻看了整个第 7 章，发现整章都在讲述回溯算法（Backtrack），包括我之前提到的 Dancing Link 实际上是一个比较优化的算法。
Dancing link大的要来喽
引言
我以前玩过一个叫智慧金字塔的儿童益智玩具，后来我发现它居然早在 NOI 2005 就出现过1了， 我还写了一个程序2专门来解这些题目， 上回说到将双向链表和 Algorithm X 结合起来就是 Dancing link了， 这次我们就来看看最关键的建模方法。
