Der schnellste Weg, um die geringste Menge an Teilmengen zu finden, die bis zu dem Gesamtsatz in Python gesenkt werden ⇐ Python

[Anonymous]

Sag, ich habe ein Wörterbuch mit solchen Sätzen: < /p>

Code: Select all

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

Jeder Satz repräsentiert eine Teilmenge eines Gesamtsatzes S = Set (Bereich (10)) . Ich möchte, dass ein effizienter Algorithmus die am wenigsten Schlüssel an Schlüssel finden, die den gesamten Satz ausmachen, und eine leere Liste zurückzugeben, wenn sie durch Kombinationen von Schlüssel nicht möglich ist. Wenn es viele mögliche Kombinationen gibt, die die geringste Menge an Schlüssel zum gesamten Set haben, benötige ich nur eine Kombination und es kann eine davon sein.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>
Dies wird jedoch sehr teuer, wenn das Wörterbuch viele Schlüssel hat (in der Praxis habe ich rund 100 Schlüssel). Irgendwelche Vorschläge für einen schnelleren Algorithmus?