提问人：tparker 提问时间：2/15/2018 更新时间：2/15/2018 访问量：297
如何迭代平衡的二进制字符串？
How can I iterate over balanced binary strings?
问：
我需要系统地遍历（偶数）长度为 n 的平衡二进制字符串集，即由相等数量的 1 和 0 组成的二进制字符串。 （这个问题可以用许多等效的方式表示;例如，给定集合 S = {1， 2， ...， n}，如何遍历 S 的平衡二分法，或大小为 n/2 的 S 子集。最有效的方法是什么？
最幼稚的算法是简单地遍历所有二进制字符串（例如，按照标准词典顺序），然后跳过所有不平衡的字符串。但这是非常低效的：有 2^n 个长度为 n 的二进制字符串，但只有 （n 选择 n/2） 是平衡的。根据斯特林的近似，这个量渐近增长为 $\sqrt{2/（\pi n）} 2^n$，因此只有一小部分 ~1/n 的二进制字符串是平衡的。
在我看来，更有效的实现可能是这样的：你从字符串 000...0111...1 开始，然后通过一系列相邻的转置 01 -> 10 将 1 跳到左边。但是我无法想出一种方法来组织转置，以便每个平衡的二进制字符串都产生一次。例如，如果你总是转置最左边的 01，那么你会错过很多字符串（例如 0110），但如果在每一步你都把每个可能的转调分支到一个树中，那么你会多计算很多字符串（例如 0101 -> 1010 可以通过按任一顺序执行两个转换来达到）。
（如果算法易于推广，能够迭代具有任意固定不平衡的 n 位二进制字符串集，那就太好了，但不是必需的。
答：
1赞
גלעד ברקן
2/15/2018
#1
下面是一个 Python 递归（可以很容易地转换为堆栈迭代;内部函数中提供了任意固定的不平衡）：g
def f(n):
def g(n, k, s):
if len(s) == n:
return [s]
if len(s) + k == n:
return [s + (n - len(s)) * '1']
if k == 0:
return [s + (n - len(s)) * '0']
return g(n, k, s + '0') + g(n, k - 1, s + '1')
return g(n, n / 2, '')
输出：
=> f(6)
=> ['000111', '001011', '001101', '001110', '010011', '010101', '010110', '011001', '011010', '011100', '100011', '100101', '100110', '101001', '101010', '101100', '110001', '110010', '110100', '111000']
评论