Eine Möglichkeit, diesen Prozess zu beschleunigen, besteht darin, schnell zu prüfen, ob die Buchstaben jedes Wortes in der Wortliste eine Untermenge der Buchstaben in Ihrer Briefliste sind. Das ist schnell, weil set-Operationen in Python schnell sind. Wenn dieser Test bestanden wird, können Sie einen langsameren Test verwenden, um sicherzustellen, dass jeder Buchstabe im Wort eine zulässige Anzahl von Malen vorkommt.
Der folgende Code verwendet die collections und itertools Module. Es kann ohne diese Module gemacht werden, aber es ist nicht so sauber. :)
Als meine Wortliste habe ich die Scrabble OD5.zip Liste von http://www.3zsoftware.com/fr/wordmagic/listes.php die 378.975 Wörter enthält (in Kleinbuchstaben, ohne Akzente); Die unkomprimierte Dateigröße beträgt 4169985 Byte.
from collections import Counter
from itertools import groupby
fname = 'french_word_list_OD5.txt'
letters = ['a', 'r', 'e', 't', 'r', 'i', 'e', 'd', 's']
letterset = set(letters)
letter_counts = Counter(letters)
found = []
with open(fname) as f:
for word in f:
word = word.strip()
# Does the word only use letters found in letterset?
if letterset.issuperset(word):
# Check that the word doesn't use too many of any letter
if all(len(list(g)) <= letter_counts[k]
for k, g in groupby(sorted(word))):
found.append(word)
print(len(found), 'solutions found')
# Sort the words by length
found.sort(key=len, reverse=True)
# Print some of the longest words
for word in found:
if len(word) < 8:
break
print(word, len(word))
Ausgang
507 solutions found
deratiser 9
deterrais 9
detireras 9
aretiers 8
asteride 8
dateries 8
deratise 8
desertai 8
desirera 8
destrier 8
deterrai 8
deterras 8
detirera 8
editeras 8
etireras 8
itereras 8
ratieres 8
reeditas 8
reiteras 8
residera 8
resterai 8
retardes 8
retersai 8
retraies 8
siderera 8
stadiere 8
stererai 8
tarieres 8
terserai 8
triedres 8
Dieser Skript dauerte weniger als 2 Sekunden auf meiner alten 2GHz Maschine. Bei der ersten Ausführung wird es etwas länger dauern, da das Betriebssystem die Datendatei zwischenspeichert.
Hier ist eine Version, die keine Module importiert.
Es prüft, ob ein Wort gültig ist, indem es über seine Buchstaben iteriert und sieht, ob jeder Buchstabe in temp ist, was eine Kopie der letters-Liste ist. Wenn ein Buchstabe in temp gefunden wird, wird er entfernt, sodass Wörter, die zu viele Buchstaben enthalten, den Test nicht bestehen.
Diese Version speichert nur die längsten Wörter, die es findet, aber es ist einfach zu ändern, so dass es alle Wörter speichert, die aus letters gemacht werden können.
fname = 'french_word_list_OD5.txt'
letters = ['a', 'r', 'e', 't', 'r', 'i', 'e', 'd', 's']
letterset = set(letters)
# A list to store the words that can be built from the permitted letters
found = []
# The length of the current longest word in `found`
hilen = 1
with open(fname) as f:
for word in f:
word = word.strip()
# Does the word only use letters found in letterset?
if letterset.issuperset(word):
# Check that the word doesn't use too many of any letter
temp = letters[:]
for c in word:
if c in temp:
temp.remove(c)
else:
break
else:
# We only get here if the `break` isn't executed
# Save word if its length is >= current longest word
wordlen = len(word)
if wordlen >= hilen:
hilen = wordlen
found.append(word)
print(len(found), 'solutions found')
# Sort the words by length
found.sort(key=len, reverse=True)
# Print only the longest words
for word in found:
if len(word) == hilen:
print(word)
Ausgang
11 solutions found
deratiser
deterrais
detireras
Dies ist eine vereinfachte Version des vorherigen. Es macht den Subset-Test nicht, was es fast doppelt so langsam macht.
fname = 'french_word_list_OD5.txt'
letters = ['a', 'r', 'e', 't', 'r', 'i', 'e', 'd', 's']
# A list to store the words that can be built from the permitted letters
found = []
# The length of the current longest word in `found`
hilen = 1
with open(fname) as f:
for word in f:
word = word.strip()
# Check that each letter in `word` is in `letters`
temp = letters[:]
for c in word:
if c in temp:
temp.remove(c)
else:
break
else:
# We only get here if the `break` isn't executed
# Save word if its length is >= current longest word
wordlen = len(word)
if wordlen >= hilen:
hilen = wordlen
found.append(word)
print(len(found), 'solutions found')
# Sort the words by length
found.sort(key=len, reverse=True)
# Print only the longest words
for word in found:
if len(word) == hilen:
print(word)
??? Warum -1 auf meine Frage ??? Wenn du nicht helfen willst pass einfach auf! –
Sie haben wahrscheinlich einen Down-Vote erhalten, weil Sie keinen Code gepostet haben und weil die Erklärung Ihres Algorithmus an einigen Stellen schwer zu verstehen ist. Es kann einfacher sein, anderen Programmierern einen Algorithmus zu erklären, der Code oder Pseudocode verwendet. –