如何遍历平衡二进制字符串？

Question

我需要系统地遍历一组（偶数）长度为 n 的平衡二进制字符串，即由相等数量的 1 和 0 组成的二进制字符串。（这个问题可以用许多等价的方式来表述；例如，给定集合 S = {1, 2, ..., n}，如何迭代 S 的平衡二分，或大小为 n/2.) 最有效的方法是什么？

最天真的算法是简单地遍历所有二进制字符串（例如，按照标准字典顺序），然后跳过所有不平衡的字符串。但这是非常低效的：有 2^n 个长度为 n 的二进制字符串，但只有 (n choose n/2) 是平衡的。根据斯特林近似值，这个数量以 $\sqrt{2/(\pi n)} 2^n$ 的形式渐近增长，因此只有一小部分 ~1/n 的二进制字符串是平衡的。

在我看来，更有效的实现可能是这样的：从字符串 000...0111...1 开始，然后通过一系列相邻的换位 01 将 1 跳到左边-> 10。但我想不出一种组织换位的方法，以便每个平衡的二进制字符串都生成一次。例如，如果你总是转置最左边的 01，那么你会遗漏很多字符串（例如 0110），但如果在每一步都将每个可能的转置分支到树中，那么你会多算很多字符串（例如 0101 ->可以通过按任一顺序执行两个转换来达到 1010）。

（如果算法很容易被推广到能够迭代具有任意固定不平衡的 n 位二进制字符串集，那会很好，但不是必需的。）

Answer 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']

如何遍历平衡二进制字符串？

How can I iterate over balanced binary strings?

language-agnostic

string

iteration

algorithm