Fastest way to generate bit permutations in Python 3.x

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

What are you actually trying to achieve with the result of this? What performance requirements do you have? — jonrsharpe
– jonrsharpe, Commented Nov 6, 2016 at 12:21
well, it's a part of solving traveling salesman problem using DP. I'm generating all 2**(n-1) subsets of the cities and then loop through them. Actually there are no performance requirements imposed on me apart from making it as fast as possible :) — Nick Slavsky
– Nick Slavsky, Commented Nov 6, 2016 at 12:25

Zero Piraeus · Accepted Answer · 2016-11-06 13:06:34Z

1

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

answered Nov 6, 2016 at 13:06

Zero Piraeus

59.7k28 gold badges158 silver badges164 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Fastest way to generate bit permutations in Python 3.x

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related