Nick Slavsky - 7 months ago 69
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
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?

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)}
``````