使用 Python bitset 查找大小为 k 的集合的所有组合

Question

我正在尝试加快我自己的旅行商动态编程解决方案。我原来的解决方案是用一个字典来记忆，字典中有一个 python frozenset() 作为键的一部分。但是，我相信可以使用位集（或者在我的实现中使用大小为 2^n 位的常规整数，其中 n 是我们图中的顶点数，第 i 位表示顶点 i 是否包含在集合中）来改进此实现。

给定一个位集，如何生成所有大小为 k 的集合？

例如：集合 = 11011，k = 3 我们应该 return： 11010 11001 10011 01011

(4选3) = 4

itertools 中的任何类似 combinations(element_set, k) 的内容，但对于位集？

Answer 1

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)

输出

使用 Python bitset 查找大小为 k 的集合的所有组合

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

python

dynamic-programming

bitset

traveling-salesman