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

Question

我正在计算 cyclic de Bruijn sequences使用以下代码:

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？代码中似乎没有任何内容可以保证这一点。

---

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

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 位末端、所有四个 2 位末端和八个 3 位末端中的六个(100 及其补码 011 将不起作用，因为它们与 0110 的组合重叠。