引言

前面几篇我们一直在和精准匹配、Dancing Link 打交道，解决的核心问题是”在组合空间里找满足条件的子集”。这篇换个方向——不是挑选，而是遍历：怎样把所有 n 位二进制串走一遍，而且每一步只改变一个 bit？

答案藏在一个中国传统智力玩具里。

九连环

九连环大概长这样：一根横杆上套着 n 个环，环与环之间有链条连接。目标很简单——把所有环从横杆上取下来。

    ┌─┐ ┌─┐ ┌─┐ ┌─┐ ┌─┐
    │○│ │○│ │○│ │○│ │○│   ← n 个环
    └┬┘ └┬┘ └┬┘ └┬┘ └┬┘
     │   │   │   │   │
═════╪═══╪═══╪═══╪═══╪═════  ← 横杆
     5   4   3   2   1      ← 编号（从右往左）

操作规则只有两条：

规则 a）最右边的环随时可以取下或装上：

    ┌─┐ ┌─┐ ┌─┐              ┌─┐ ┌─┐
    │○│ │○│ │○│              │○│ │○│
    └┬┘ └┬┘ └┬┘              └┬┘ └┬┘
     │   │   │        →       │   │    ┌─┐
═════╪═══╪═══╪═════      ═════╪═══╪════│○│══
     3   2   1                3   2    └─┘
   状态: 111                状态: 110    ↑ 环1取下

规则 b）其他任意一个环，当且仅当它右边紧邻的那个环在杆上、而右边更远的所有环都不在杆上时，才能操作：

    ┌─┐ ┌─┐                     ┌─┐
    │○│ │○│                     │○│
    └┬┘ └┬┘                     └┬┘
     │   │            →          │
═════╪═══╪════════      ═════════╪════════
     3   2                       2
   状态: 110                  状态: 010
   环2在✓ 环1不在✓            ↑ 环3取下

换句话说，要操作第 k 个环（从右往左数，k > 1），你必须让第 k-1 个环在杆上，而第 k-2, k-3, … 全部离杆。这个约束让问题远没有看起来那么简单。

问题：n 个环，最少需要多少步才能全部取下？

手动拆解

先从小的开始。用 1 表示环在杆上，0 表示不在，最左边是第 n 个环（最”深”的），最右边是第 1 个环。

n = 1：直接取下。1 步。

n = 2：先取环 1，再取环 2。2 步。（状态变化：11 → 10 → 00）

n = 3：这里有意思了。

步骤 状态 操作
0 111 初始
1 110 取环 1
2 010 取环 3（环 2 在，环 1 不在 ✓）
3 011 装环 1
4 001 取环 2（环 1 在，无更右环 ✓）
5 000 取环 1

5 步完成。递归结构已经浮现了：要拆 n 个环，先拆掉环 1 到 n-2（腾出空间），操作第 n 个环，再装回环 1 到 n-2（为拆第 n-1 个做准备），最后拆前 n-1 个。用 T(n) 表示最少步数：

\[T(n) = T(n-2) + 1 + T(n-2) + T(n-1) = T(n-1) + 2T(n-2) + 1 \tag{1}\]

从 01 串到格雷码

回头看 n=3 的状态序列：

111 → 110 → 010 → 011 → 001 → 000

每相邻两个状态之间，恰好只有一位不同。这不是巧合——操作规则本身就要求每步只能动一个环。

但更有趣的是：这 6 个状态只经过了 8 个 3-bit 串中的 6 个，少了 100 和 101。是九连环”到不了”这两个状态吗？

不是。九连环的规则实际上定义了一条经过所有 \(2^n\) 个状态的路径。只不过 111 并不在路径的端点——完整的路径是：

000 - 001 - 011 - 010 - 110 - 111 - 101 - 100

111 在路径中间（位置 5），所以从 111 走到 000 只需要往左走 5 步，而 101 和 100 在它右边，不需要经过。

这条路径有一个名字：格雷码（Gray code）。

正式定义：一个 n 位格雷码是 \(2^n\) 个 n-bit 二进制串的一个排列 \(v_0, v_1, \ldots, v_{2^n-1}\)，使得相邻两个串 \(v_k\) 和 \(v_{k+1}\) 之间恰好有一位不同。九连环的状态转移图恰好就是这样一条路径——从 \(0\ldots0\) 到 \(10\ldots0\)，经过所有 \(2^n\) 个状态，每步只改一位。

格雷码以 Frank Gray 命名（1953 年贝尔实验室专利），但法国法官 Louis Gros 早在 1872 年就通过分析九连环发现了它。Knuth 在 TAOCP 中特意指出：Gros is “the true inventor of Gray binary code”。

反射构造法

格雷码怎么构造？最优雅的方式是反射法（reflected construction）。

设 \(\Gamma_n\) 是 n 位格雷码序列，定义：

\[\Gamma_0 = \varepsilon \text{（空串）}\] \[\Gamma_{n+1} = 0\Gamma_n, \; 1\Gamma_n^R \tag{2}\]

其中 \(\Gamma_n^R\) 是 \(\Gamma_n\) 的逆序，\(0\Gamma_n\) 表示在每个串前面加 0，\(1\Gamma_n^R\) 表示在逆序的每个串前面加 1。

展开看看：

n=1: \(\Gamma_1 = 0, 1\)

n=2: \(\Gamma_2 = 0\Gamma_1, 1\Gamma_1^R = 00, 01, 11, 10\)

n=3: \(\Gamma_3 = 0\Gamma_2, 1\Gamma_2^R = 000, 001, 011, 010, 110, 111, 101, 100\)

注意 \(\Gamma_3\) 的前半部分和后半部分像镜子一样对称——后半是前半的”倒影”加上首位从 0 变成 1。这就是”反射”的含义。

为什么这和九连环对应？因为九连环的递归拆解正好就是反射构造的递归结构：拆 n 个环时，你先处理了前 n-1 个环的所有状态（对应 \(0\Gamma_{n-1}\)），然后操作第 n 个环（首位从 0 变 1），再把前 n-1 个环的状态倒着走一遍（对应 \(1\Gamma_{n-1}^R\)）。

反射构造还给出了一个极简的公式。格雷码的第 k 个元素可以直接算：

\[g(k) = k \oplus \lfloor k/2 \rfloor \tag{3}\]

其中 \(\oplus\) 是异或运算。用 Python 一行搞定：

def gray(k):
    return k ^ (k >> 1)

比如 gray(0)=0, gray(1)=1, gray(2)=3, gray(3)=2, gray(4)=6, gray(5)=7, gray(6)=5, gray(7)=4，写成二进制就是 000, 001, 011, 010, 110, 111, 101, 100，和上面 \(\Gamma_3\) 一模一样。

Algorithm G

有了公式 (3) 当然可以生成格雷码，但 Knuth 在 TAOCP 中给出了一个更巧妙的在线算法 Algorithm G，它不需要计算 \(g(k)\)，而是维护一个奇偶位（parity bit）来决定每一步翻转哪一位。

算法的核心逻辑是：

  • 如果当前 parity 是偶数，翻转最右边那一位（第 0 位）
  • 如果当前 parity 是奇数，找到最右边的 1，翻转它左边那一位

然后把 parity 取反。就这么简单。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

def algorithm_g(n):
    """Generate all n-bit Gray code using Knuth's Algorithm G."""
    a = [0] * (n + 1)  # a[0..n-1] is the n-tuple, a[n] is sentinel
    # G1: Initialize
    parity = 0
    while True:
        # G2: Visit
        yield a[:n]

        # G3: Choose j
        if parity == 0:
            j = 0
        else:
            # Find rightmost 1, then go one position left
            k = 0
            while a[k] == 0:
                k += 1
            j = k + 1

        # G4: Complement coordinate j
        if j == n:
            break  # Terminate: we've visited all 2^n tuples
        a[j] = 1 - a[j]
        parity = 1 - parity

逐步解读：

  • G1（第 3-5 行）：初始化 n-tuple 全为 0，parity 为 0。额外分配 a[n] 作为哨兵。
  • G2（第 8 行）：输出当前 n-tuple。
  • G3（第 11-16 行）：如果 parity 是偶数，\(j=0\)（翻转最右位）。如果是奇数，找最右边的 1 的位置 \(k\)，令 \(j=k+1\)。当 \(j=n\) 时说明所有 \(2^n\) 个串都已访问，算法结束。
  • G4（第 20-21 行）：翻转 \(a_j\)，parity 取反。

跑一下 n=4 看看：

for code in algorithm_g(4):
    print(''.join(map(str, reversed(code))))  # 高位在前

输出：

0000
0001
0011
0010
0110
0111
0101
0100
1100
1101
1111
1110
1010
1011
1001
1000

16 个 4-bit 串全部出现，相邻两个恰好差一位。注意 1111 出现在第 10 个位置（从 0 开始数），所以 4 个环的九连环从 1111 拆到 0000，就是沿这条路径往回走 10 步——和我们后面要算的 T(4) = 10 完全吻合。

最少步数

回到开篇的问题。

我们已经知道，九连环的状态图就是一条格雷码路径，从 \(0\ldots0\) 到 \(10\ldots0\)，共 \(2^n\) 个节点、\(2^n - 1\) 条边。\(1\ldots1\)（全部在杆上）在这条路径的某个中间位置，设它到 \(0\ldots0\) 的距离为 T(n)。

利用反射构造的递归结构可以推出一个优雅的关系。在 \(\Gamma_n\) 中，\(1\ldots1\)（n 个 1）出现在后半段 \(1\Gamma_{n-1}^R\) 中，对应 \(\Gamma_{n-1}^R\) 里的 \(1\ldots1\)（n-1 个 1）。由于逆序的关系：

\[T(n) = 2^{n-1} + (2^{n-1} - 1 - T(n-1)) = 2^n - 1 - T(n-1) \tag{4}\]

也就是说 \(T(n) + T(n-1) = 2^n - 1\)。解这个递推得到闭合公式：

\[T(n) = \left\lfloor \frac{2^{n+1} - 1}{3} \right\rfloor \tag{5}\]

验证一下：\(T(1)=1, T(2)=2, T(3)=5, T(4)=10, T(5)=21, T(6)=42, T(7)=85\)。

7 个环需要 85 步——难怪古人说”解得开，解不开”。有趣的是，John Wallis 在 1693 年就指出，如果从状态 \(10\ldots0\) 出发（只有最深的环在杆上），拆解反而更难——需要走完整条路径，共 \(2^n - 1\) 步。而日常的”全部在杆上”起点 \(1\ldots1\) 恰好在路径中间偏后的位置，所以步数大约是 \(2^n\) 的 \(\frac{2}{3}\)。

预告

格雷码远不止一种。标准反射格雷码只是最经典的一个，还有 balanced（每一位翻转次数尽量均匀）、monotonic（黑白棋子重心单调移动）、complementary（前后半互补）等各种变体。下一篇我们来看 Knuth 的 Algorithm L——一个用 focus pointers 实现的无循环（loopless）格雷码生成算法，每一步严格 O(1) 时间，和 Dancing Link 的指针技巧异曲同工。