引言

我发现在以前的回溯算法中，很少提到链表的使用，虽然 Dancing link 算法已经用的炉火纯青了，但介绍它属于是“跳级”了，咱们既然从零单排回溯算法，那还要从链表在回溯中的简单用法讲起，这就要提 Langford 对的生成了。

Langford 对是一个组合数学中的概念。给定一个正整数 ，Langford 对是将数字 1 到 n 的每个数字重复两次，并以一种特定的方式排列，使得两个相同的数字之间恰好间隔等于该数字的位置数。 例如，对于 n=4，一种可能的 Langford 对排列是 23421314。在这里，每个数字重复两次，且两个 1 之间间隔 1 个位置；两个 2 之间间隔 2 个位置；以此类推。

青铜回溯

废话不多说，直接手撕代码。

1
2
3
4
5
6
7
8

    sorted_num = sorted(remaining)
    for num in sorted_num:
    if pos + num + 1 < 2 * n and sequence[pos + num + 1] == 0:
    sequence[pos] = sequence[pos + num + 1] = num
    remaining.remove(num)
    results.extend(backtrack(sequence, remaining))
    remaining.add(num)
    sequence[pos] = sequence[pos + num + 1] = 0

remaining 保留了剩余的数字，每次取出一个填入数组 sequence 第一个为 0 的位置，填入时要做 2 件事：

  1. 更新 sequence 的 2 个位置
  2. 把 num 从 remaining 删除

白银优化

说实话，如果不是为了展示链表的快速修改和恢复，我觉得上面的代码已经够用了。 这里我直接引用 Knuth 在 7.2.2 中的算法 L，它的步骤如下：

  1. 初始化，p 的每个元素依次指向后一个元素，并且最后的 $p_n\leftarrow0$
  2. 进入第 $i$ 层，令 $k\leftarrow p_0$，如果 $k=0$ 那么找到一组解，跳到第 5 步，否则令 $j\leftarrow0$，当$x_i<0$令$i\leftarrow i+1$
  3. 尝试$x_i$，这时 $k=p_j$ 并且 $i$ 位是空位，如果 $i+k+1>2n$，跳到第 5 步，否则如果$x_{i+k+1}=0$，令$x_i\leftarrow k, x_{i+k+1}\leftarrow-k,y_i\leftarrow j,p_j\leftarrow p_k$
  4. 接着尝试，令$j\leftarrow k, k\leftarrow p_j$，如果$k\neq0$ 回到第 3 步继续尝试
  5. 回溯，令$i\leftarrow i-1$。当$i>0 \And x_i<0$则$i\leftarrow i-1$，然后令$k\leftarrow x_i, x_i\leftarrow0, x_{i+k+1}\leftarrow0, j\leftarrow y_i, p_j\leftarrow k$，回到第 4 步。否则算法结束

黄金恢复

除了 $x$ 记录 Langford 数组状态，额外要用到2个数组：

  • $y_i$: 在第 $i$ 步时，链表中的位置
  • $p_i$: 链表，初始时 $p_i\leftarrow i+1$，最后$p_n\leftarrow0$ 这里比较费解的地方在第 3 步尝试和第 5 步回溯，通过之前的 从零单排回溯算法 algorithm B 我们可以看到 $i$ 在这里表示层数，也就是进行到第 $i$ 位，在进入下一层之前，要记录 $y_i$ 并且改变链表，注意巧妙的一点是：链表从始至终都是存在数组里，增删只改变指向的值。改造后的代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

    def backtrack_link(n):
        def enter(i):
            # step L2
            k = p[0]
            if k == 0:
                result.append(x[:])
                return
            else:
                j = 0
                while x[i] < 0:
                    i += 1
            # step L3 try x[i] = k
            while k > 0:
                if i + k + 1 >= 2*n:
                    return
                elif x[i+k+1] == 0:
                    x[i] = k
                    x[i+k+1] = -k
                    y[i] = j
                    p[j] = p[k]
                    enter(i+1)
                    # step L5 backtrack
                    p[y[i]] = k
                    x[i] = x[i+k+1] = 0
                # step L4 try again
                j = k
                k = p[j]

        # step L1
        x = [0] * (2 * n)
        y = [0] * (2 * n)
        p = [k+1 for k in range(n)]
        p.append(0)
        i = 1
        result = []
        enter(0)
        return result

看了代码你也许会说这比前面【青铜回溯】还多了一个数组，代码长度还增加了不少，到底优化在哪呢？从执行效率来说这次比【青铜回溯】确实没什么长进，但关键我们要理解这里用链表来记录回溯位置以及并不需要真的删除创建元素，这和精准匹配 中的 Algorithm X 有异曲同工之妙，这也是让白银优化进阶成黄金的原因。

尾声

下次我们会继续回溯之旅，来完成另一个用到指针来优化恢复的例子——comma free code。

习题

如果你看过之前的dancing link和精准匹配，那么试着为“生成 1-n 的 Langford 对”进行建模吧。