51 votes

Algorithme pour générer des anagrammes

Quelle serait la meilleure stratégie pour générer des anagrammes.

An anagram is a type of word play, the result of rearranging the letters
of a word or phrase to produce a new  word or phrase, using all the original
letters exactly once; 
ex.
  • Onze plus deux est un anagramme de Douze plus un
  • Un point décimal est un anagramme de Je suis un point en place
  • Astronomes est un anagramme de Étoiles de lune

Au premier abord, cela semble simple, il suffit de mélanger les lettres et de générer toutes les combinaisons possibles. Mais quelle serait l'approche efficace pour générer uniquement les mots du dictionnaire ?

Je suis tombé sur cette page, Résoudre les anagrammes en Ruby .

Mais quelles sont vos idées ?

44voto

FogleBird Points 23405

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.

19voto

Jason Cohen Points 36475

Pour chaque mot du dictionnaire, classez les lettres par ordre alphabétique. Ainsi "foobar" devient "abfoor".

Ensuite, lorsque l'anagramme d'entrée arrive, triez également ses lettres, puis cherchez-le. C'est aussi rapide qu'une consultation de table de hachage !

Pour les mots multiples, vous pourriez faire des combinaisons des lettres triées, en triant au fur et à mesure. Toujours beaucoup plus rapidement que de générer toutes les combinaisons.

(voir les commentaires pour plus d'optimisations et de détails)

8voto

hazzen Points 7315

Voir ceci affectation du département CSE de l'Université de Washington.

En gros, vous avez une structure de données qui contient simplement les comptes de chaque lettre dans un mot (un tableau fonctionne pour l'ascii, passez à une carte si vous voulez un support unicode). Vous pouvez soustraire deux de ces ensembles de lettres ; si un compte est négatif, vous savez qu'un mot ne peut pas être l'anagramme d'un autre.

5voto

Tyler Points 16516

Pré-traitement :

Construisez un tableau dont chaque feuille est un mot connu, classé par ordre alphabétique.

Au moment de la recherche :

Considérer la chaîne d'entrée comme un multiset. Trouvez le premier sous-mot en parcourant la trie d'index comme dans une recherche en profondeur. À chaque branche, vous pouvez vous demander si la lettre x se trouve dans le reste de mon entrée. Si vous disposez d'une bonne représentation du multiset, cette requête devrait se faire en temps constant (en principe).

Une fois que vous avez le premier sous-mot, vous pouvez garder le multiset restant et le traiter comme une nouvelle entrée pour trouver le reste de cet anagramme (s'il existe).

Augmentez cette procédure avec la mémorisation pour des recherches plus rapides sur les multi-ensembles à reste commun.

C'est assez rapide - chaque traversée de trie est garantie pour donner un sous-mot réel, et chaque traversée prend un temps linéaire dans la longueur du sous-mot (et les sous-mots sont généralement très petits, selon les normes de codage). Cependant, si vous vraiment Si vous voulez quelque chose d'encore plus rapide, vous pouvez inclure tous les n-grammes dans votre pré-traitement, où un n-gramme est une chaîne de n mots à la suite. Bien sûr, si W = #mots, alors vous passerez de la taille d'index O(W) à O(W^n). Peut-être que n = 2 est réaliste, en fonction de la taille de votre dictionnaire.

4voto

dF. Points 29787

Je ne l'ai pas regardé en détail, mais ce Utilitaire UNIX de recherche d'anagrammes comprend un PDF avec la source (domaine public, C++) et une discussion partie par partie.

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by:

X