Trouver les anagrammes d'un mot donné

Je suis venu avec une nouvelle solution je pense. Il utilise le Théorème Fondamental de l'Arithmétique. L'idée est donc d'utiliser un tableau de 26 premiers nombres premiers. Ensuite, pour chaque lettre dans le mot d'entrée nous obtenons le correspondant de nombre premier A = 2, B = 3, C = 5, D = 7 ... et puis nous calculons le produit de notre mot d'entrée. Ensuite, nous faisons cela pour chaque mot dans le dictionnaire, et si un mot correspond à notre mot d'entrée, puis on l'ajoute à la liste des résultats. Tous les anagrammes possèdent la même signature, car

Tout entier plus grand que 1 est un nombre premier, ou peut être écrit
comme un produit de nombres premiers (sans tenir compte de l'ordre).

Voici le code. - Je convertir le mot en MAJUSCULES et 65 ans est la position de l'Un qui correspond à mon premier nombre premier:

private int[] PRIMES = new int[] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31,
        37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103,
        107, 109, 113 };

C'est la méthode:

 private long calculateProduct(char[] letters) {
    long result = 1L;
    for (char c : letters) {
        if (c < 65) {
            return -1;
        }
        int pos = c - 65;
        result *= PRIMES[pos];
    }
    return result;
}

Bien Essaie de le rendre plus facile à vérifier si le mot existe.
Donc, si vous placez l'ensemble de dictionnaire dans un trie:

http://en.wikipedia.org/wiki/Trie

ensuite vous pourrez par la suite prendre la parole et faire simple retour en arrière en prenant un char et de façon récursive de vérifier si l'on peut "marcher" en bas de la Trie avec tout combiniation du reste de la station (ajout d'un char à un moment). Lorsque tous les caractères sont utilisés dans une récursivité de la branche et il y avait un chemin d'accès valide dans la Trie, puis le mot existe.

La Trie aide parce que son une belle condition d'arrêt:
Nous pouvons vérifier si la partie de la chaîne, de l'e.g "Anag" est un chemin d'accès valide dans la trie, si l'on peut briser particulier la récursivité de la branche. Cela signifie que nous n'avons pas de vérifier chaque permutation des caractères.

En pseudo-code

checkAllChars(currentPositionInTrie, currentlyUsedChars, restOfWord)
    if (restOfWord == 0)
    {
         AddWord(currentlyUsedChar)
    }
    else 
    {
        foreach (char in restOfWord)
        {
            nextPositionInTrie = Trie.Walk(currentPositionInTrie, char)
            if (nextPositionInTrie != Positions.NOT_POSSIBLE)
            {
                checkAllChars(nextPositionInTrie, currentlyUsedChars.With(char), restOfWord.Without(char))
            }
        }   
    }

Évidemment vous avez besoin d'une belle Trie discbased qui vous permet de progressivement à "marcher" en bas de l'arbre et de vérifier à chaque nœud si il y a un chemin avec le char à tout nœud suivant...

• Réduire les mots à dire - les minuscules (clojure.string/lower-case).
• Les classer (group-by) par lettre de la fréquence de la carte (frequencies).
• Baisse de la fréquence des cartes,
• ... laissant les collections des anagrammes.

(These) sont les fonctions correspondantes dans le dialecte de Lisp Clojure.

L'ensemble de la fonction peut être exprimée ainsi:

(defn anagrams [dict]
  (->> dict
       (map clojure.string/lower-case)
       (group-by frequencies)
       vals))

Par exemple,

(anagrams ["Salt" "last" "one" "eon" "plod"])
;(["salt" "last"] ["one" "eon"] ["plod"])

Une fonction d'indexation qui fait correspondre chaque chose à sa collection est

(defn index [xss]
  (into {} (for [xs xss, x xs] [x xs])))

De sorte que, par exemple,

((comp index anagrams) ["Salt" "last" "one" "eon" "plod"])
;{"salt" ["salt" "last"], "last" ["salt" "last"], "one" ["one" "eon"], "eon" ["one" "eon"], "plod" ["plod"]}

... où comp est la fonctionnelle de la composition de l'opérateur.

Qui dépend de la façon dont vous stockez votre dictionnaire. Si c'est un simple tableau de mots, pas d'algorithme sera plus rapide que linéaire.

Si elle est triée, puis ici, c'est une approche qui peut fonctionner. Je l'ai inventé tout à l'heure, mais je suppose que c'est plus rapide que l'approche linéaire.

1. Désigner votre dictionnaire D, préfixe courant que les S. S = 0;
2. Vous créez de la fréquence de la carte pour votre mot. Permet de dénoter par F.
3. À l'aide de binaires de recherche, de trouver des pointeurs de début de chaque lettre dans le dictionnaire. Permet de désigner ce tableau de pointeurs par P.
4. Pour chaque char c de A à Z, si F[c] == 0, l'ignorer, d'autre
   • S += c;
   • F[c] --;
   • P <- pour chaque personnage, je P[i] = pointeur sur premier mot commençant par S+i.
   • Récursive appelez l'étape 4 jusqu'à ce que vous trouver une correspondance pour votre mot ou jusqu'à ce que vous trouver qu'une telle correspondance.

C'est comment j'allais le faire, de toute façon. Il devrait y avoir une approche plus conventionnelle, mais c'est plus rapide, puis linéaire.

• Calculer la fréquence de comptage vecteur pour chaque mot dans le dictionnaire, un vecteur de longueur de l'alphabet liste.
• générer un vecteur aléatoire Gaussien de la longueur de l'alphabet liste

• projet de chaque mot du dictionnaire du comte de vecteur dans cette direction au hasard et de stocker la valeur de (insérez tels que le tableau de valeurs est triée).

• Donné un nouveau test de la parole, du projet dans la même direction au hasard utilisé pour les mots du dictionnaire.

• Faire un binaire de recherche pour trouver la liste des mots que la carte de la même valeur.
• Vérifier si chaque mot obtenu comme ci-dessus est en effet un vrai anagramme. Si pas, le retirer de la liste.
• Revenir le reste des éléments de la liste.

PS: La procédure ci-dessus est une généralisation du premier numéro de procédure qui peuvent potentiellement conduire à un grand nombre (et donc de calcul de la précision des questions)

D'abord vérifier si la longueur des chaînes de caractères sont les mêmes.
ensuite, vérifiez si la somme des caractères les chaînes de caractères sont les mêmes (c'est à dire le code ascii somme)
puis les mots sont des anagrammes
d'autre pas un anagramme