为什么这个 de Bruijn 代码的最后几位总是 return 0

Question

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，因此 "last" 三个数字为 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 序列。但是，如果您 do 提前用完该序列，那么您将无法将部分序列扩展到 16 位。四个匹配位很简单：7 位序列 0001000 现在是死胡同。需要更多的工作来证明其他启动，但它是相同的一般原则：仅达到完整 16 位的 forced 已保存所需的环绕序列。

查看 0110 案例以了解可能性的范围：各种解决方案均采用两个 1 位末端、所有四个 2 位末端和八个 3 位末端中的六个（100 及其补码 011 将不起作用，因为它们与 0110).

的组合重叠

为什么这个 de Bruijn 代码的最后几位总是 return 0

Why does this de Bruijn code always return 0s for the last few bits

python

algorithm

combinatorics

discrete-mathematics