“你们中有多少人开除过下属？”一句话掷地有声，全场面面相觑。斯坦福商学院系主任站在我面前，扫视了一圈未来的商界精英们，缓缓的说：“所有新晋管理者最害怕、逃避做的事情就是Firing。”这句话我记忆犹新，没想到一年以后就轮到我来唱黑脸。公司有个资…

数学中存在这样一个序列，它充满魔力，在实际工程中也有一部分的应用。今天就打算分享一下这个序列，它在 Google S2 中是如何使用的以及它在图论中，其他领域中的应用。这个序列就是德布鲁因序列 De Bruijn。

一. 从一个魔术开始说起

有这样一个扑克牌魔术。魔术师手上拿着一叠牌，给5个人(这里的人数只能少于等于32，原因稍后会解释)分别检查扑克牌，查看扑克牌的花色和点数是否都是不同的，即没有相同的牌。

检查完扑克牌，没有重复的牌以后，就可以给这5个人洗牌了。让这5个人任意的抽一叠牌从上面放到下面，即切牌。5个人轮流切完牌，牌的顺序已经全部变化了。

接着开始抽牌。魔术师让最后一个切牌的人抽走这叠牌最上面的一张，依次给每个人抽走最上面的一张。这时候抽走了5张牌。魔术师会说，“我已经看透了你们的心思，你们手上的牌我都知道了”。然后魔术师会让拿黑色牌的人站起来(这一步很关键！)。然后魔术师会依次说出所有人手上的牌。最后每个人翻出自己的牌，全部命中。全场欢呼。

在整个魔术中，有两个地方比较关键。第一个是参与的人数只能少于等于32 。一副完整的扑克牌中，总共有54张牌，但是除去2张鬼牌(因为他们花色只有2种)，总共就52张牌。

在上述魔术中，所有的牌都用二进制进行编码，要想任意说出任意连续的5张牌，那么必须这副牌具有全排列的特性。即枚举所有种组合，并且每个组合都唯一代表了一组排列。

如果窗口大小为5，5张连续的扑克牌。二进制编码 2^5^ = 32 ，所以需要32张牌。如果窗口大小为6，6张连续的扑克牌，二进制编码 2^6^ = 64，需要64张扑克牌。总共牌只有52张，所以不可能到64张。所以32个人是上限了 。

第二个关键的地方是，只有让拿黑色的牌的人或者拿红色的牌的人站出来，魔术师才能知道这5个人拿到的连续5张扑克牌究竟是什么。其实魔术师说“我已经知道你们所有人拿到的是什么牌”的时候，他并不知道每个人拿到的是什么牌。

扑克牌除了点数以外，还有4种花色。现在需要32张牌，就是1-8号牌，每号牌都有4种花色。花色用2位二进制编码，1-8用3位二进制编码。于是5位二进制正好可以表示一张扑克牌所有信息。

如上图，00110 表示的就是梅花6 。11000 表示的是红桃8（因为没有 0 号牌，所以000就表示8）

第一步将扑克牌编码完成以后，第二步就需要找到一个序列，它必须满足以下的条件：由 2^n-1^个1和2^n-1^个0构成的序列或者圆排列，是否能存在在任意 n 个位置上0，1序列两两都不同。满足这个条件的序列也称为 n 阶完备二进圆排列。

这个魔术中我们需要找的是 5 阶完备二进圆排列。答案是存在这样一个满足条件的序列。这个序列也就是文章的主角，德布鲁因序列。

上述序列就是一个窗口大小为5的德布鲁因序列。任意连续的5个二进制相互之间都是两两不同的。所以给观众任意洗牌，不管怎么洗牌，只要最终挑出来是连续的5张，这5张的组合都在最终的结果之中。

将窗口大小为5的德布鲁因序列每5个二进制位都转换成扑克牌的编码，如下：

所以32张牌的初始顺序如下：

梅花8，梅花A，梅花2，梅花4，黑桃A，方片2，梅花5，黑桃3，方片6，黑桃4，红桃A，方片3，梅花7，黑桃7，红桃7，红桃6，红桃4，红桃8，方片A，梅花3，梅花6，黑桃5，红桃3，方片7，黑桃6，红桃5，红桃2，方片5，黑桃2，方片4，黑桃8，方片8。

将所有的排列组合列举出来，如上图。当魔术师让黑色或者红色的牌的人出列的时候，就能确定到具体是哪一种组合了。于是也就可以直接说出每个人手上拿的是什么牌了。

这个魔术中选取的德布鲁因序列也非常特殊，是可以通过一部分的递推得到。

这个特殊的序列，任意取出其中一个窗口，即5个连续的二进制，5个二进制的第一位和第三位，或者倒数第三位和倒数第五位相加，加法遵循二进制规则，即可得到这个窗口紧接着的下一位。

如上图的例子，假设当前窗口里面的五位是 00001，左数第一位加上第三位，或者右数第三位加上第五位，得到的是0，那么这个窗口紧接着的后一位就是0 ，即 000010 。再举一个例子，当前窗口里面是 11000 ，左数第一位加上第三位为1，所以紧接着的下一位是1，即 110001 。

三. 德布鲁因序列的定义和性质

德布鲁因序列(De Bruijn sequence)，记为B(k, n)，是 k 元素构成的循环序列。所有长度为 n 的 k 元素构成序列都在它的子序列（以环状形式）中，出现并且仅出现一次。

德布鲁因序列的长度为 k^n^。

注意到，所有长度为 n 的 k 元素构成的序列总共有 k^n^。而对于德布鲁因序列中的每个元素，恰好构成一个以此元素开头长度为 n 的子序列。所以德布鲁因序列的长度为 k^n^ 。

我们用数学归纳法证明一下上述的结论。

我们先假设德布鲁因序列是二进制的，即 k = 2。想计算序列数量总共有多少个，其实可以看这个序列每个子序列转换成10进制的数最大的是多少，那么就是它的数量。

由于每相邻的子序列是相互依赖的关系，比如下一个子序列是前一个子序列左移一位再加上 0 或者 1，产生下一个子序列。当然最后要 mod 2^n^，这样控制每个子序列的长度都在 n 位之间。于是我们可以得到这样的一个式子：

利用错位相减法，我们可以得到通项公式：

最后利用数学归纳法我们可以得到一个通用的式子，即：

最最常用的德布鲁因序列就是 k = 2 。计算一下 |B(2,n)| 的数量，如下：

由于德布鲁因序列并不唯一，所以用代码可以生成其中的任意一种。

二进制的德布鲁因序列用的比较多，接下来看看它生成的序列。

B(2，1) 就唯一一种情况。

B(2，2) 由4位二进制位组成。也是唯一一种情况。

B(2，3) 由8位二进制位组成。有2种德布鲁因序列。

B(2，4) 由16位二进制位组成。对应有16种德布鲁因序列。

B(2，5) 由32位二进制位组成。对应有2048种德布鲁因序列。由于太多了，这里没法一一列举出来，任意挑选一个出来举例：

B(2，6) 由64位二进制位组成。对应有67,108,864种德布鲁因序列。由于太多了，这里没法一一列举出来，任意挑选一个出来举例：

B(2，5) 和 B(2，6) 在实际生产中都有广泛的用途。

四. 在图论中的应用：欧拉回路 和 汉密尔顿回路

在图论中，有这样一种无向连通图，有一条通路，能经过这个图的每条边一次并且仅一次的路径被称为欧拉回路。这个问题也是最常见的哥尼斯堡七桥问题：能不能一次走遍所有的7座桥，并且每座桥只经过一次。其实就是判断是否存在欧拉回路。

与欧拉问题非常类似的是汉密尔顿回路的问题。该问题起源于英国数学家威廉汉密尔顿（Willian Hamilton）于1857年发明的一个关于正十二面体的数学游戏：正十二面体的每个棱角上标有一个当时非常有名的城市，游戏的目的是“环绕地球”旅行，也就是说，寻找一个环游路线使得经过每个城市一次且恰好一次。

如果把正十二面体的20个棱角看成图中的顶点，将正十二面体画成如上图的平面图，那么问题就转换成：能否在图中找到一条回路，经过每个顶点一次有且仅有一次。上图就给出了一条符合要求的回路。

欧拉回路的问题一般求解方法有两种，DFS 和 Fleury 佛罗莱算法。但是汉密尔顿图没有一个有效的判断方法，它只是给出了一些充分条件或者必要条件，并非充要条件。

德布鲁因序列 和 欧拉回路，汉密尔顿回路 有紧密的联系。

若由 k 种符号组成的所有长度为 n 的序列列表为有向图的顶点，则图中有 k^n^ 个顶点， 若顶点 m 去掉第一个符号并在尾端添加一个符号便可得顶点 n ，则有一个有向边由 m 指向 n，此时图就是 德布鲁因图。如下图，k = 2， n = 3 的图中，顶点 010 有两条对外的边，分别指向 101 和 100 。

在德布鲁因图中的汉密尔顿回路 即为 德布鲁因序列。如下图，左图中红色的汉密尔顿回路 ，图中对应的德布鲁因序列是 ，且这个汉密尔顿回路等价于窗口长度为 2 的德布鲁因序列中的一个欧拉回路，见下右图中标记的欧拉回路对应的顺序编号。

所以，窗口为 n 的德布鲁因图中的汉密尔顿回路可以等价转换为窗口为 n - 1 的德布鲁因图中的欧拉回路。

当然，一个德布鲁因图中的汉密尔顿回路并不一定唯一。如上左图，同样是 k = 2，n = 3 的德布鲁因图，还可以找到一条汉密尔顿回路。对应的欧拉回路的顺序也对应的发生了变化，见右图。

这也说明了，k = 2，n = 3 的时候，德布鲁因序列存在多个，并不唯一。

再进一步，既然说高阶的德布鲁因图的汉密尔顿回路可以转换成低级的欧拉回路。那么我们就用 k = 2，n = 3 的德布鲁因图的欧拉回路去构造高阶的汉密尔顿图，可以么？答案是当然可以。

如上图，用 k = 2，n = 3 的德布鲁因图中的一条欧拉回路，我们构造出了 k = 2，n = 4 的德布鲁因序列。

同理，当 k = 3，n = 2 的时候，德布鲁因图中依旧可以找到一条汉密尔顿回路，与之对应的 n = 1 的窗口的欧拉回路也存在。如下图。

德布鲁因序列用的比较广泛的一点应用就是 位扫描器。在 Google S2 中也是这个作用。

先来看一个比较常见的问题。

有一个非0的正数，它用二进制表示的。问如何快速的找到它二进制位中最后的1所在的位置。例如，0100，它的最后一个1所在的位置是从右往左数的第2位(从0开始数)。

这道题有几种做法，从粗糙到最优依次分析分析。

最直接的想法是能把这个二进制数转换成只有一位为1的情况。如果上面这个问题转换成只有一个位上为1的情况，那很好解决。

那么问题转化为如何把末尾的1分离出来。如果这个数只有2个位置上为1，可以直接用位运算进行分离。

通过上面的操作可以把最后一位的1分离出来。

分离出来以后的解法就很多种了。

可以用 for 循环，不断的右移目标数。

这种方式简单粗暴，时间复杂度为 O(n) 。

把上述循环改成二分，时间复杂度就变成了 O(lgn)

3. 构造特殊数字进行位运算

这种方式看上去比较巧，但是实际还是利用了二分搜索的思想。

这种方式的时间复杂度也是 O(lgn) ，但是实际计算会比二分搜索快很多，因为它不需要比较运算，都位运算即可完成。

这种方式就比之前的方式都要高效了。

假设 x 有32位，所以末尾的1出现的可能只有32种。如果 x 为64，那就是64种可能，每一位上都有可能。通过哈希的方式 O(1) 的时间复杂度查询出结果。

这种方式的原理也是哈希，但是这种方式比单纯的哈希要快，因为它避免的取余的计算。

如果 x 为32位，那么哈希函数可以构造成下面这样：

构造这样一个哈希函数有2点优点：

1. 二进制数本身是二的次方，所以任何一个数字乘以这个二进制的数，都相当于左移运算。
2. 德布鲁因序列相当于是全排列，枚举了所有的情况。所以它的两两子序列之间肯定不相同，这就是完美的哈希。

最后又移动27位是为了保证能取出开头的5位。

在 Go 的原生代码包中，有一个 nat.go 文件，在这个文件里面有这样一段代码：

在这个文件中，同样有一个函数在解决上述的问题，只不过它换了一个角度。

求一个二进制数的末尾1所在的位置，其实可以转化为求这个二进制数末尾连续0有多少个的问题。

这个经典的问题在图灵奖获得者 Donald Ervin Knuth 的著作 《计算机程序设计艺术》的第四卷，section 7.3.1 上有，感兴趣的同学可以看看这个问题。

deBruijn32 和 deBruijn64 分别是德布鲁因序列。两两之间的子序列都是不相同的，并且所有的子序列构成了一个全排列。

我们用下面的哈希函数构造一个“完美”的哈希函数。

那么数组里面存的值就是我们最终的结果了，即末尾1所在的位置或者末尾连续有多少个0 。

其实数组里面存的数字是这样算出来的：

即把算出来的哈希值作为下标，对应下标存储的值是左移的位数。这个左移的位数就是我们要的结果。所以先算哈希值，然后通过数组取出哈希值里面存储的值即为我们的结果了。

上述程序和之前的实现方式完全一致，只不过这里函数名的意义代表查找末尾1的位置，和查找末尾有多少个0，完全一致！

上述代码也是 Google S2 中的源码，它也是直接利用德布鲁因序列来查找末尾1所在的位。

De Bruijn 序列的奇妙不仅体现在魔术上。我们还可以使用它为机器人做路标定位：将两种不同颜色的小方块排成一条长线摆在机器人行进的路上，机器人只要识别出自己前后的几个方块是什么颜色，既不需要GPS，也不需要高精度探测仪，就可以知道自己走了多少米。

研究人员利用 De Bruijn 序列设计了每次可以产生一个用于加密的不同随机数字的简单电子元件“反馈移位寄存器”，上一个随机数字和下一个随机数字之间只改变一个数位和移位一下就可以，电路构造非常简单。

在测量工程上，德布鲁因序列还可以用在基于光栅投影模式的三维形貌快速测量系统研究中。

在基因工程中，德布鲁因序列可以用在基因组重复区域组装上。

在人工智能算法中，神经网络时间序列预测也有德布鲁因序列的身影。

---

---