python dynamic-programming bitset traveling-salesman

Using Python bitset to find all combinations of a set of size k

I am trying to speed up my own dynamic programming solution for Travelling Salesman. My original solution memoizes with a dictionary with a python frozenset() as part of the key. However, I believe that this implementation can be improved using bitsets (or in my implementation a regular integer of size 2^n bits where n is the number of vertices in our graph and ith bit represents whether vertex i is included in the set).

Given a bitset, how can I generate all sets of size k?

Ex: set = 11011, k = 3 We should return: 11010 11001 10011 01011

(4 choose 3) = 4

Anything like combinations(element_set, k) from itertools but for bitsets?

Solution

from itertools import combinations

def generate_combinations(indices_repr, k):
    total_items = range(len(indices_repr))
    choice_items = [x for x in total_items if indices_repr[x] == '1']
    for choosen_items in combinations(choice_items, k):
        x = ['0' for i in range(len(indices_repr))]
        for item in choosen_items:
            x[item] = '1'
        yield ''.join(x)


for indices_repr in generate_combinations('11011', 3):
    print(indices_repr)

Output