关于De Bruijn序列生成代码中两个条件作用的技术咨询

完整代码 #

# De Bruijn sequences return...
# Generate strings using DFS, ignoring strings with "seen" subsequences

def S(arrange, seen, N):
    # len(arrange) can be removed if 00000 is marked as seen
    if len(arrange) == 2**N and 2*arrange.count(0) == 2**N:
        print(''.join(map(str, arrange)))

    for c in (0, 1):
        new_seen = seen[:]
        new_arrange = arrange + [c]

        word = ''.join(map(str, new_arrange[-N:]))
        seen_i = int(word, 2)

        if not new_seen[seen_i]:
            new_seen[seen_i] = 1
            S(new_arrange, new_seen, N)


S([0]*5, [0]*2**5, 5)  # Beginning must be 00000

问题解答 #

1. 条件2*arrange.count(0) == 2**N的作用

这个条件用来强制生成的序列中0和1的数量完全相等。推导可知：2*arrange.count(0) == 2**N等价于arrange.count(0) = 2^(N-1)，此时序列总长度是2**N，所以1的数量为2**N - 2^(N-1) = 2^(N-1)，两者数量完全一致。

添加这个条件是因为De Bruijn序列B(2,N)的结构要求0和1的出现次数对称，它可以过滤掉长度达标但01数量失衡的无效序列，确保输出符合定义的De Bruijn序列。

2. 条件if not new_seen[seen_i]的作用

这是DFS递归的核心剪枝条件，目的是保证每个N位二进制子串（即De Bruijn序列定义中的N元组）只被使用一次：

• 先取当前序列的最后N位组成二进制串，转成整数seen_i作为索引（总共有2**N个不同的N元组，刚好对应0到2**N-1的索引范围）
• new_seen[seen_i]标记该N元组是否已被使用，只有当它未被使用时，才会标记为已使用并继续递归。

猜想确认 #

• 前者确实用于统计0和1的数量相等：没错，通过等式推导可直接得出0和1的数量均为2^(N-1)，完全相等。
• 后者不是DFS递归的基础条件（终止条件）：DFS的终止条件是开头的if len(arrange) == 2**N and ...，这个条件是递归的分支筛选逻辑，用来避免重复使用N元组，属于剪枝操作，保证生成过程符合De Bruijn序列的要求。

内容的提问来源于stack exchange，提问作者kevin