La plupart de ces réponses sont terriblement inefficaces et/ou ne donnent que des solutions à un mot (sans espace). Ma solution permet de traiter n'importe quel nombre de mots et est très efficace.
Ce que vous voulez, c'est une structure de données trie. Voici une complet Implémentation de Python. Vous avez juste besoin d'une liste de mots enregistrée dans un fichier nommé words.txt
Vous pouvez essayer la liste de mots du dictionnaire Scrabble ici :
http://www.isc.ro/lists/twl06.zip
MIN_WORD_SIZE = 4 # min size of a word in the output
class Node(object):
def __init__(self, letter='', final=False, depth=0):
self.letter = letter
self.final = final
self.depth = depth
self.children = {}
def add(self, letters):
node = self
for index, letter in enumerate(letters):
if letter not in node.children:
node.children[letter] = Node(letter, index==len(letters)-1, index+1)
node = node.children[letter]
def anagram(self, letters):
tiles = {}
for letter in letters:
tiles[letter] = tiles.get(letter, 0) + 1
min_length = len(letters)
return self._anagram(tiles, [], self, min_length)
def _anagram(self, tiles, path, root, min_length):
if self.final and self.depth >= MIN_WORD_SIZE:
word = ''.join(path)
length = len(word.replace(' ', ''))
if length >= min_length:
yield word
path.append(' ')
for word in root._anagram(tiles, path, root, min_length):
yield word
path.pop()
for letter, node in self.children.iteritems():
count = tiles.get(letter, 0)
if count == 0:
continue
tiles[letter] = count - 1
path.append(letter)
for word in node._anagram(tiles, path, root, min_length):
yield word
path.pop()
tiles[letter] = count
def load_dictionary(path):
result = Node()
for line in open(path, 'r'):
word = line.strip().lower()
result.add(word)
return result
def main():
print 'Loading word list.'
words = load_dictionary('words.txt')
while True:
letters = raw_input('Enter letters: ')
letters = letters.lower()
letters = letters.replace(' ', '')
if not letters:
break
count = 0
for word in words.anagram(letters):
print word
count += 1
print '%d results.' % count
if __name__ == '__main__':
main()
Lorsque vous exécutez le programme, les mots sont chargés dans un trie en mémoire. Ensuite, il suffit de taper les lettres que vous voulez rechercher et le programme imprimera les résultats. Il n'affichera que les résultats qui utilisent toutes les lettres saisies, rien de plus court.
Il filtre les mots courts de la sortie, sinon le nombre de résultats est énorme. N'hésitez pas à modifier l'option MIN_WORD_SIZE
réglage. Gardez à l'esprit qu'en utilisant simplement "astronomes" comme entrée, on obtient 233 549 résultats si MIN_WORD_SIZE
est de 1. Vous pouvez peut-être trouver une liste de mots plus courte qui ne contient que des mots anglais plus courants.
De même, la contraction "I'm" (dans l'un de vos exemples) n'apparaîtra pas dans les résultats, à moins que vous n'ajoutiez "im" au dictionnaire et que vous ne définissiez l'option MIN_WORD_SIZE
à 2.
L'astuce pour obtenir plusieurs mots consiste à revenir au nœud racine du tableau chaque fois que vous rencontrez un mot complet dans la recherche. Ensuite, vous continuez à parcourir le tableau jusqu'à ce que toutes les lettres aient été utilisées.