Trouver des anagrammes pour un mot donné

j'ai trouvé une nouvelle solution, je suppose. 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. Puis pour chaque lettre dans le mot d'entrée nous obtenons le nombre premier Correspondant 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 auront la même signature parce que

tout entier supérieur à 1 est soit un nombre premier, soit peut être écrit comme un produit unique de nombres premiers (ignorant 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;
}

nous savons que si deux mots n'ont pas la même longueur, ce ne sont pas des anagrammes. Ainsi, vous pouvez diviser votre dictionnaire en groupes de mots de la même longueur.

Maintenant, nous nous concentrons sur un seul de ces groupes et, fondamentalement, tous les mots ont exactement la même longueur dans ce petit univers.

si chaque position de lettre est une dimension, et la valeur dans cette dimension est basée sur la lettre (par exemple le code ASCII). Ensuite, vous pouvez calculer la longueur du mot vecteur.

par exemple, dire'A' =65, 'B' = 66, puis length("AB") = sqrt(65*65 + 66*66). Évidemment, length("AB") = length("BA").

Clairement, si deux mots sont des anagrammes, puis leurs vecteurs ont la même longueur. La question suivante est, si deux vecteurs de mot (du même nombre de lettres) ont la même longueur, sont-ils des anagrammes? Intuitivement, je dirais non, puisque tous les vecteurs de cette longueur forment une sphère, il y en a beaucoup. Pas sûr, puisque nous sommes dans l'espace entier dans ce cas, combien il y en a réellement.

mais au moins, il vous permet de cloisonner votre dictionnaire encore plus loin. Pour chaque mot de votre dictionnaire, calculez la distance du vecteur: for(each letter c) { distance += c*c }; distance = sqrt(distance);

Ensuite créer une carte pour tous les mots de longueur n, et avec la distance et la valeur est une liste de mots de longueur n qui donnent cette distance particulière.

Vous allez créer une carte pour chaque distance.

Ensuite, votre recherche devient l'algorithme suivant:

1. utilisez le corriger la table des dictionnaires en fonction de la longueur du mot
2. Calculez la longueur du vecteur de votre mot
3. rechercher la liste des mots qui correspondent à cette longueur
4. parcourez la liste et choisissez les anagrammes en utilisant un algorithme naïf est maintenant la liste des candidats est grandement réduite

bien essayer rendrait plus facile de vérifier si le mot existe. Donc, si vous mettez tout le dictionnaire dans un tri:

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

ensuite, vous pouvez prendre votre parole et faire un simple retour en arrière en prenant un char et en vérifiant récursivement si nous pouvons "marcher" le long du Trie avec n'importe quelle combinaison du reste des char (ajoutant un char à la fois). Quand tous les caractères sont utilisés dans une branche de récursion et qu'il y avait un chemin valide Trie, alors le mot existe.

Le Trie aide parce que c'est une belle condition d'arrêt: On peut vérifier si la partie d'une corde, E. g "Anag" est un chemin valide dans le trie, sinon nous pouvons briser cette branche de récursion pérticulaire. 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 structure de données qui vous permet de "marcher" progressivement le long de l'arbre et de vérifier à chaque noeud si il y a un chemin avec le char à tout nœud suivant...

static void Main(string[] args)
{

    string str1 = "Tom Marvolo Riddle";
    string str2 = "I am Lord Voldemort";

    str2=  str2.Replace(" ", string.Empty);
    str1 = str1.Replace(" ", string.Empty);
    if (str1.Length != str2.Length)
        Console.WriteLine("Strings are not anagram");
    else
    {
        str1 = str1.ToUpper();
        str2 = str2.ToUpper();
        int countStr1 = 0;
        int countStr2 = 0;
        for (int i = 0; i < str1.Length; i++)
        {
            countStr1 += str1[i];
            countStr2 += str2[i];

        }
        if(countStr2!=countStr1)
            Console.WriteLine("Strings are not anagram");
        else Console.WriteLine("Strings are  anagram");

    }
    Console.Read();
}

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

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

toute 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 indexation fonction qui relie 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 l'opérateur de composition fonctionnelle.

générer toutes les permutations est facile, je suppose que vous êtes inquiet que vérifier leur existence dans le dictionnaire est la partie "hautement inefficace". Mais cela dépend en fait de la structure de données que vous utilisez pour le dictionnaire: bien sûr, une liste de mots serait inefficace pour votre cas d'utilisation. En parlant de Essaie, ce serait probablement une représentation idéale, et assez efficace, aussi.

une Autre possibilité serait de faire quelques pré-traitement sur votre dictionnaire, par exemple, construisez un hashtable où les clés sont les lettres du mot triées, et les valeurs sont des listes de mots. Vous pouvez même sérialiser ce hashtable de sorte que vous pouvez l'écrire dans un fichier et le recharger rapidement plus tard. Alors pour chercher des anagrammes, il vous suffit de trier votre mot donné et recherchez l'entrée correspondante dans la table de hachage.

Cela 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, alors voici 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. indique que votre dictionnaire est D, le préfixe courant est S. S = 0;
2. vous créez la carte de fréquence pour votre mot. Dénotons-le par F.
3. utilisation de la recherche binaire trouver des pointeurs pour commencer chaque lettre dans le dictionnaire. Permet de dénoter ce tableau de pointeurs par P.
4. pour chaque char c de A à Z, si F[c] == 0, sautez-le, sinon
   • 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 comme ça que je le ferais, de toute façon. Il devrait y avoir un approche plus conventionnelle, mais plus rapide que linéaire.

essayé de mettre en œuvre la solution hashmap

public class Dictionary {

    public static void main(String[] args){

    String[] Dictionary=new String[]{"dog","god","tool","loot","rose","sore"};

    HashMap<String,String> h=new HashMap<String, String>();

    QuickSort q=new QuickSort();

    for(int i=0;i<Dictionary.length;i++){

        String temp =new String();

        temp= q.quickSort(Dictionary[i]);//sorted word e.g dgo for dog

        if(!h.containsKey(temp)){
           h.put(temp,Dictionary[i]);
        }

        else
        {
           String s=h.get(temp);
           h.put(temp,s + " , "+ Dictionary[i]);
        }
    }

    String word=new String(){"tolo"};

    String sortedword = q.quickSort(word);

    if(h.containsKey(sortedword.toLowerCase())){ //used lowercase to make the words case sensitive

        System.out.println("anagrams from Dictionary   :  " + h.get(sortedword.toLowerCase()));
    }

}

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

• projeter le vecteur de comptage de chaque mot du dictionnaire dans cette direction aléatoire et stocker la valeur (insérer de façon à ce que le tableau des valeurs soit trié).

• avec un nouveau mot d'essai, projetez-le dans la même direction aléatoire que celle utilisée pour le dictionnaire mot.

• faites une recherche binaire pour trouver la liste des mots qui correspondent à 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.
• retourner les éléments restants de la liste.

PS: la procédure ci-dessus est une généralisation de la procédure des nombres premiers qui peut conduire à de grands nombres (et donc à des problèmes de précision de calcul)

une solution est - Faites correspondre les nombres premiers aux caractères alphabétiques et multipliez le nombre premier

For ex - 

    a -> 2
    b -> 3
    ......
    .......
    ......
    z -> 101

'ab' -> 6
'ba' -> 6
'bab' -> 18
'abba' -> 36
'baba' -> 36

obtenir MUL_number pour mot donné. retournez tous les mots du dictionnaire qui ont le même MUL_number que le mot donné

Vérifiez D'abord si la longueur des chaînes est la même. vérifiez ensuite si la somme des caractères dans les deux chaînes est la même (c'est-à-dire la somme du code ascii).) puis les mots sont des anagrammes sinon pas d'anagramme!--1-->