Nick Slavsky Nick Slavsky - 1 month ago 24
Python Question

Fastest way to generate bit permutations in Python 3.x

I need to generate all possible N choose K N-bit numbers where K bits are set.
The best and most concise option that I was able to come up with is extremely slow:

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)
took 8.3s on my machine.

How can I make it faster? For example, maybe there is a way to set all the bits in bulk, without looping through all of them?

Answer

Your kbits(25, 12) is calculating 12 of the same 25 powers of 2 more than five million times, when it only needs to calculate each of them once (and having done so, can use the sum() builtin rather than building results piecemeal).

Here's a much shorter solution, which is also about 3x faster on my machine:

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