python - 在 Python 3.x 中生成位排列的最快方法

Question

我需要生成所有可能的 N 选择 K N 位数字，其中设置了 K 位。我能想出的最好和最简洁的选项是非常慢的:

def kbits(n, k):
    result = set()
    for bits in itertools.combinations(range(n), k):
        s = 0
        for bit in bits:
            s |= 1 << bit
        result.add(s)
    return result

kbits(25, 12) 在我的机器上用了 8.3s。

如何让它更快？例如，也许有一种方法可以批量设置所有位，而无需遍历所有位？

Answer 1

您的 kbits(25, 12) 正在计算相同的 25 次方中的 12 次超过 500 万次，而它只需要对它们中的每一个计算一次(并且这样做之后，可以使用 sum() 内置函数而不是零碎地构建结果)。

这是一个更短的解决方案，在我的机器上也快了大约 3 倍:

def kbits(n, k):
    powers = [1 << e for e in range(n)]
    return {sum(bits) for bits in itertools.combinations(powers, k)}