如何生成指定长度、固定0和1数量的所有0-1组合列表

你之前使用itertools.product全量枚举再筛选的方案复杂度为O(2^{n)，n=106时2}106属于天文数字，完全无法在普通设备上运行。

最优实现思路 #

符合要求的序列本质是从总长度的n个位置中，选k个位置放1（剩余位置放0，k=总长度-0的数量），直接用组合生成工具即可无冗余生成所有目标序列，运算量仅和有效组合数C(n,k)成正比，没有任何无效计算。

代码实现 #

import itertools

def generate_target_combinations(total_length: int, zero_num: int):
    one_num = total_length - zero_num
    # 遍历所有放1的位置组合
    for one_positions in itertools.combinations(range(total_length), one_num):
        # 初始化全0列表
        res = [0] * total_length
        for pos in one_positions:
            res[pos] = 1
        # 用生成器返回，不占内存
        yield res

测试验证 #

用你给出的示例参数测试：

# 总长度4，0的数量2
combinations = list(generate_target_combinations(4, 2))
print(combinations)
# 输出：[[1,1,0,0], [1,0,1,0], [1,0,0,1], [0,1,1,0], [0,1,0,1], [0,0,1,1]]
# 所有组合和你要求的完全一致，仅排列顺序不同，若需要和示例顺序对齐，改成选zero_num个位置放0即可

注意事项 #

1. 代码采用生成器实现，不会一次性加载所有组合到内存，即使组合数很大也不会占用过多内存，适合逐个处理组合的场景，不要转换成list全量存储。
2. 如果你的场景中0和1的数量差异较大，可以选择数量更少的元素来选位置，进一步降低运算量：比如总长度106仅需要3个1，就选3个位置放1；如果仅需要3个0，就选3个位置放0。
3. 若0和1的数量接近总长度的一半（比如总长度106，1的数量为53），组合数C(106,53)≈1e31，属于数学上的极大量级，无论用什么方法都不可能遍历完所有组合，这种场景建议调整需求，改为抽样生成部分组合即可。

内容的提问来源于stack exchange，提问作者Daniel Bodas Romero