Самый быстрый способ найти наименьшее количество подмножеств, которое подходит к общему набору в Python ⇐ Python

[Anonymous]

Скажем, у меня есть словарь таких наборов, как это: < /p>

Код: Выделить всё

d = {'a': {1,2,8}, 'b': {3,1,2,6}, 'c': {0,4,1,2}, 'd': {9}, 'e': {2,5},
'f': {4,8}, 'g': {0,9}, 'h': {7,2,3}, 'i': {5,6,3}, 'j': {4,6,8}}

Каждый набор представляет подмножество общего набора s = set (range (10)) . Я бы хотел, чтобы эффективный алгоритм обнаружил, что меньше всего клавиш, составляющих весь набор, и вернуть пустой список, если это невозможно при каких -либо комбинациях ключей. Если есть много возможных комбинаций, которые имеют наименьшее количество клавиш, подходящих для всего набора, мне нужна только одна комбинация, и это может быть любая из них.import copy
def append_combinations(combo, keys):
for i in range(len(keys)):
new_combo = copy.copy(combo)
new_combo.append(keys)
new_keys = keys[i+1:]
if {n for k in new_combo for n in d[k]} == s:
valid_combos.append(new_combo)
append_combinations(new_combo, new_keys)

valid_combos = []
combo = []
keys = sorted(d.keys())
append_combinations(combo, keys)
sorted_combos = sorted(valid_combos, key=lambda x: len(x))
print(sorted_combos[0])
# ['a', 'c', 'd', 'h', 'i']
< /code>
Однако это становится очень дорого, когда в словаре есть много ключей (на практике у меня будет около 100 ключей). Есть предложения для более быстрого алгоритма?

Подробнее здесь: https://stackoverflow.com/questions/796 ... tal-set-in