De Bruijin序列与魔术（四）——De Bruijin序列的拓展结果

早点关注我，精彩不错过！

在上一讲中，我们解释了对扩展De Bruijin序列用来变魔术的思路和公式，相关内容请戳：

De Bruijin序列与魔术（三）——De Bruijin序列的拓展思考

De Bruijin序列与魔术（二）——魔术《De Bruijin序列》

De Bruijin序列与魔术（一）——De Bruijin序列简介

那搜寻结果到底如何呢？今天就来揭晓！

De Bruijin扩展序列搜索和应用结果

回顾一下上期定下来的搜索De Bruijin图中子圈序列的递推公式：

a_l = (a_(l - n) + a(l - n + m)) % k，m = 1:(n - 1)

以及基本的De Bruijin图：

图1 De Bruijin图

经过运行，和我想象的一样，这样的序列就是会有大量的结果，在众多结果中，也确实发现了很多几百上千长度的序列，对我们的魔术就没什么作用了。在仔细搜寻过程中，D(2, n)系列的还有好几个长度为31的圈。不过我们原始的这个已经够用了，其他的要不就才10几要不就很大了。和13接近的也有，但是其最大长度 2 ^ n都很大了。即虽然长度约摸满足，但是怎么往回编码到值范围有限的扑克牌花色点数是个大问题。而D(4, n)以及更大的k时的情况，和我想的一样，其总编码范围k ^ n都太大了不方便编码，哪怕找到的子圈长度合适我也得放弃了。

其实D(3, n)系列我一开始是觉得最没用的，因为3进制实在是从人脑熟悉程度到编码难度都很大，也容易使得序列总编码范围太大而难用。D(3, 3)的长度为13的一个圈和D(3, 6)的长度为26的圈引起了我的注意：

D(3, 3) deduce by 1 len 13 vs 27:

0010111220121

D(3, 6) deduce by 2 len 26 vs 729:

00000100010101020200010201

令我一开始眼前一样的点自然是13和26的长度，刚好和一个花色的13个点数和半幅牌配合了起来，但是D(3, 6)得到的729的总长度还是让我退缩了，重点放在了D(3, 3)上。然后我就欣喜地发现，这两个序列里2的出现次数都是3次，我敏感地发现，这不恰好就可以用扑克牌中特殊的3张花牌来代表编码吗？

于是我整理思路，把这13个3进制值对应的熟悉的十进制数写了下来（每3位3进制数编码对应的第1个位置的值）：

1 3 10 4 13 14 17 24 19 5 16 9

因为本来数值范围就在0~26，从里面取的13个数不能直接对应到1~13也是正常的，我们需要找一个这13个数到1~13的一个一一映射，而且方便记忆或计算。

一眼看去这些数大大小小的都有，分布还算均匀，于是为方便观察，我便直接把它们按大小顺序排列以后，直接都除以2，奇迹就出现了：

1 3 4 5 9 10 13 14 16 17 19 21 24

0.5 1.5 2 2.5 4.5 5 6.5 7 8 8.5 9.5 10.5 12

然后再啪啪来个四舍五入：

1 2 2 3 5 5 7 7 8 9 10 11 12

好像离真正的1~13还有点距离，但是已经十分接近了，我们可以写出由这些值映射到1~13的通项公式了：

c = [(p + 1) / 2] + 1，p = 1:13；特别地，p = 1， 3， 9和13时，c = [(p + 1) / 2]，其中p为3位3进制编码的原始数值，

乍一看，你这一共才13项的公式，就有4个特例，也太水了吧？其实令人惊喜的是，那4个特例规律十分明显，就是其3进制表示的值仅有1和3个1的总共4种情况，还是很好记忆的。

于是有了这个De Bruijin序列上的合适长度的子图，又找到了方便的映射公式，本来就有好算的递推公式，那这个扑克牌的点数序列就已经出炉了：

1 2 6 3 7 8 10 k j 4 9 q 5

这个序列的扑克牌点数值就我们的编码大计还剩下最后一步，我们怎么借助这些扑克牌的点数，还加上花色，去编码原对应位上的三进制码值呢？

这最后的难题一点也不好解决，因为这些值虽然和原来的三进制数有关系，但是和们对应的三进制表达的mod 9，也就是首位之间到底要怎样才能对过去呢？要知道，从序列解码对应的n位k进制结果，可是Debruijin序列魔术解码的第一步。

都到这儿了，总不至于功亏一篑吧？我在探索数学魔术的路上，经常遇到各式各样的看起来绝对是死胡同的情况，却始终相信，一定能解决，一定能解决。越努力，运气就会越好。我这时候想起了最开始看上序列的原因，不就是那3个2恰好对应3张花牌嘛，如果真的这么编码，试试是否可行呢？

真的是奇迹，那3个2位置对应的3位3进制编码的值依次为24, 19和21，对应的编码扑克牌值刚好是13, 11和12，那可不就是这些值在扑克牌枚举值里的名字，K，J和Q么！

说是巧其实也有很直观的原因的，因为我们的解码函数基本是个近似的线性正相关的函数，所以最大的3个数自然也是3进制最大的3个数，那最大的可不就是最高位打满为2的么，唯一的巧合是刚好3个，刚好3个！

于是我们用是否花牌就可以编码2了，其余两个依照类似思路，感觉只需要划定一个大小切分的阈值，就可以编码0和1了。真是一试就中啊！这些数字里刚好有4个0，6个1，而那4个0的位置刚好编码的3位三进制数的值都是首位为0的，具体是1, 3, 4和5，对应的扑克点数就刚好是1~4，那不就是最符合直觉的，就让最小的1~4编码0，5~10编码1呗。

所以到此，整个序列的编码规律是这样的，任意连续3张牌，根据其在1~4，5~10，j~k的范围确定其一阶编码，再根据其解码公式就可以得到第一张牌的值了。至于剩下两张，可根据递推关系式得出后面位置的编码组成移位以后的新3位编码，进而算出其映射的扑克牌值来。

不过吧，说这么多，其实还不如直接把这个序列直接像牌序一样记下来呢，作为一个可索引可递推的一个观众未知但是魔术师知晓的一个牌序来使用。

从13到52的变化

当然这只是13张牌的排序，全程是花色无关的，扩展到52张的全牌十分容易，你把这个13张牌的序看作是一个内部的C13的循环，乘上C4的花色，不就是整个扑克牌序列了么？所以这也可以看作是一个Si Stebbins Stack的一种超过等模差序列的一种构造方式，依然具有递推性，周期性这些全部性质，只不过数值上的等差性没有了罢了，可以对照着之前的Si Stebbins Stack的魔术的各种原理一看就知道哪些能直接迁移过来了。

说到Si Stebbins Stack的拓展，其实除了这里用De Bruijin序列的特殊应用之外，还有一种通用的扩展方式。在dani daortiz的my personal stack中介绍了这种方法。有点类似于在《Si Stebbins Stack中的数学与魔术（四）——如何快速得到一个Si Stebbins Stack》里介绍的完美洗牌得到Si Stebbins的一个扩展，完全可以以任何值设置一组4张牌以内的公差d1, d2和d3，最后一个取1 - (d1 + d2 + d3)为下一个公差，如此和花色一同循环，即为所求。

于是从这个视角看，我们发明的基于De Bruijin序列的牌序，也只是这个拓展方式的一个对偶特例罢了，因为这里是要求把连续14张组成的13个公差的和为0（即任意一个13个数的排列）剩下的则是花色的13个划分的和为1。而魔术师们还会在其中埋下几个由替换构造的不满足规律的点，以使得规律在数学家面前完全无所适从，这也是my personal stack里的一个魔术亮点，有兴趣的同学可以自行阅读。

不过吧，这么一大段的思考，最后的结论也只是一个暗含着一个非凡通信密码的长度为13的序列而已，加上花色扩展到52张，构成一个扩展的Si Stebbins Stack而已。而如果要完成类似De Bruijin序列魔术的效果，也有更加好的魔术方法，直接利用递推关系，看了前一张，就连问哪些是红黑（这里还要问是否是花牌，6~10，更难）也省了。于是这里的魔术使用价值就真的不大了，完全有更好的方案代替，背后的精妙数字逻辑，也可以通过简单的背诵就加以完成。但这并不能抹去这些思考的意义，数学魔术，表演服务于魔术，思考服务于数学。

好了，这个系列眨眼就讲了这么多了，相信对大家了解De Bruijin的数学和魔术的方方面面应该是足够了，我们下一个精彩内容见！

我们是谁：

MatheMagician，中文“数学魔术师”，原指用数学设计魔术的魔术师和数学家。既取其用数学来变魔术的本义，也取像魔术一样玩数学的意思。文章内容涵盖互联网，计算机，统计，算法，NLP等前沿的数学及应用领域；也包括魔术思想，流程鉴赏等魔术内容；以及结合二者的数学魔术分享，还有一些思辨性的谈天说地的随笔。希望你能和我一起，既能感性思考又保持理性思维，享受人生乐趣。欢迎扫码关注和在文末或公众号留言与我交流！