如何高效生成长度为n、1到n个比特位为1的所有bitset组合

你提到的翻转0位的递推特性可以直接用来优化实现，复用前一轮的计算结果，避免每轮独立生成组合，比原有逐个调用combinations的方案效率更高，n越大优势越明显。

注意你的原有代码存在明显bug：allCombos 最后返回的是循环变量k，而非存储结果的ret。

核心实现代码 #

def allCombos(n):
    result = {}
    # 初始化k=1的所有单1位bitset
    result[1] = set(1 << i for i in range(n))
    # 从k=1递推生成k=2到k=n的结果
    for k in range(1, n):
        current_group = result[k]
        next_group = set()
        for bitset in current_group:
            # 遍历所有位，翻转0位得到下一级bitset
            for bit_idx in range(n):
                if not (bitset & (1 << bit_idx)):
                    next_group.add(bitset | (1 << bit_idx))
        result[k+1] = next_group
    return result

方案说明 #

• 原有方案每轮调用itertools.combinations都是独立生成k元组，没有复用之前的计算结果，存在冗余计算
• 递推方案完全利用了你提到的特性：k个1的bitset翻转任意一个0位，就能得到k+1个1的bitset，用集合自动去重即可，整体时间复杂度和生成所有组合的理论下限O(2^n)一致
• 如果需要输出题目示例中的固定长度二进制字符串格式，可以加一层转换：

def to_bin_strings(result, n):
    return {k: {f"{val:0{n}b}" for val in group} for k, group in result.items()}

调用示例：

print(to_bin_strings(allCombos(4), 4))

输出和你给出的示例完全匹配。

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