如何生成含K个固定位的N位二进制数的所有排列？

嘿，这个问题我之前也碰到过——直接遍历所有N位二进制数再校验确实太笨了，尤其是N大的时候完全没法用。咱们换个思路，直接构造符合要求的数，而不是大海捞针！

核心思路 #

常规解法的问题在于做了大量无用功：明明很多位已经固定了，还要遍历所有可能的组合。高效的做法应该是：

1. 先定位所有未固定的比特位（也就是fixed数组中值为-1的位置），假设一共有M = N - K个这样的位置；
2. 生成所有M位的二进制数（从0到2^M - 1），每个数对应未固定位的一组取值；
3. 把这些取值填充到预先设置好的固定模板里，直接得到符合要求的N位二进制数。

举个实际例子 #

就拿题目里的情况来说：

• N=3，fixed = {-1, 0, -1}（中间位固定为0，第一位和第三位自由）
• 未固定位是索引0和2（假设我们从左到右计数，对应二进制数的高位到低位），M=2；
• 生成所有2位二进制数：00、01、10、11；
• 把每组值填充到模板的对应位置：
  • 00 → 索引0填0，索引2填0 → 000
  • 01 → 索引0填0，索引2填1 → 001
  • 10 → 索引0填1，索引2填0 → 100
  • 11 → 索引0填1，索引2填1 → 101
    完全和题目给出的结果一致！

代码实现（Python示例） #

下面是一段可直接运行的代码，帮你快速实现这个逻辑：

def generate_fixed_binary_numbers(fixed):
    n = len(fixed)
    # 找出所有未固定的位置索引
    free_positions = [i for i, val in enumerate(fixed) if val == -1]
    m = len(free_positions)
    # 生成所有可能的自由位组合（从0到2^m -1）
    for num in range(0, 1 << m):
        # 初始化结果为固定模板的列表
        result = fixed.copy()
        # 把num的二进制位填充到自由位置
        for i, pos in enumerate(free_positions):
            # 取出num的第i位（从右往左数）
            bit = (num >> i) & 1
            result[pos] = bit
        # 把列表转成字符串输出
        yield ''.join(map(str, result))

# 测试题目中的例子
fixed = [-1, 0, -1]
for binary in generate_fixed_binary_numbers(fixed):
    print(binary)

运行这段代码，输出就是：

000
001
100
101

为什么这个方法更高效？ #

假设N=30，K=25，那自由位M=5，我们只需要生成32个数；而常规解法要遍历2^30（超过10亿）个数，效率差了好几个数量级！这个思路完全避开了无效的遍历，只针对需要变化的位做操作，性能提升非常明显。

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