为什么这个 de Bruijn 代码总是在最后几位返回 0

Question

我使用以下代码计算循环的de Bruijn序列：

import sys
if len(sys.argv) > 1:
n = int(sys.argv[1])  # get n from the command line
else:
n = 4
N = 2**n
count = 0
def debruijn(x):
if x.find(x[-n:]) < len(x)-n:  # check if last n chars occur earlier in the string
return
if len(x) == N+n-1:
print(x[:N], x[N:])
return
debruijn(x+"0")
debruijn(x+"1")

x = "0"*n
debruijn(x)
print("sequences")

这给出了：

0000100110101111 000
0000100111101011 000
0000101001101111 000
0000101001111011 000
[...]

作为输出。为什么x[N:]总是等于 000？代码中似乎没有任何内容可以保证这一点。

---

根据@Prune的要求发布到 https://math.stackexchange.com/questions/3339778/why-does-searching-for-a-non-cyclic-de-bruijn-sequence-always-give-you-a-cyclic

Answer 1

这是一个循环序列：根据定义，最后 (n-1( 位与第一个 (n-1( 位匹配。x[:(n-1)] == x[-(n-1):]

由于您强制将第一个数字0000，因此"最后"三个数字是000。 尝试更改初始序列，看看：

debruijn("0110")

输出：

0110000100111101 011
0110000101001111 011
0110000101111010 011
0110000111101001 011
0110010000111101 011
0110010100001111 011
0110010111101000 011
0110011110100001 011
0110100001011110 011
0110100001111001 011
0110100101111000 011
0110100111100001 011
0110101111000010 011
0110101111001000 011
0110111100001010 011
0110111100101000 011

为什么有效？

您唯一检查代码是查看当前的 last-4 序列是否已使用。 为什么这足以保证全面成功？

就其本身而言，它没有：您可以轻松地从00001000开始，在尾部消耗您想要的1000序列。 但是，如果您确实提前用完了该序列，那么您将无法将部分序列扩展到 16 位。 四个匹配位是微不足道的：7 位序列0001000现在是一个死胡同。 在其他开始时证明这一点需要更多的工作，但它是相同的一般原则：唯一达到完整 16 位的那些被迫保存所需的环绕序列。

查看0110的情况，了解可能性的范围：各种解决方案采用 1 位端、所有 4 个 2 位端和 8 个 3 位端中的 6 个(100及其补码，011由于它们与0110的组合重叠而不起作用(。