Nick Slavsky - 2 months ago 39

Python Question

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

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