Programmiererforum

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

Sag, ich habe ein Wörterbuch mit solchen Sätzen: < /p>
[code]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}}
[/code]
Jeder Satz repräsentiert eine Teilmenge eines Gesamtsatzes S = Set (Bereich (10)) . Ich möchte, dass ein effizienter Algorithmus die [b] am wenigsten [/b] 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[i])
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?