obtenir la liste des anagrammes à partir d'un dictionnaire
Fondamentalement, les Anagrammes sont comme permutation de la chaîne.E.g stack
,sackt
,stakc
tous sont des anagrammes de stack
(la pensée ci-dessus les mots ne sont pas significatives). De toute façon, vous pourriez avoir compris ce que j'ai simplement voulu dire.
Maintenant, je veux une liste de anagrams
donné millions de mots, ou tout simplement dire à partir d'un dictionnaire.
Ma question de base est Find total number of unique anagrams in a dictionary?
De tri et de comparaison
ne fonctionnera pas comme il est l'heure de la complexité est assez mauvais.
J'ai pensé à l'aide de la table de hachage, de la chaîne en tant que clé.
Mais le problème, c'est ce que devrait être la fonction de hachage ? Il serait utile si certains pseudo-code
fourni. Quelques autres approches mieux que les approches mentionnées serait également utile.
Grâce.
- question de ne pas horriblement clair. pouvez-vous s'il vous plaît reformuler l'objectif?
- Voulez-vous dire: j'ai un dictionnaire de un million de mots, je tiens à identifier tous les jeux de mots dans le dictionnaire, qui sont des anagrammes les uns des autres? E. g. Si le dictionnaire de contenus: [tap, pat, pot, top] vous souhaitez voir [[tap, pat], [pot, haut de la page]]?
- ouais @Alex .Je veux juste combien d'anagrammes sont là ?
- j'espère que mon objectif est clair pour vous.
- Le tri est la solution ici, et sa complexité est linéaire si l'on suppose une constante de limite à la longueur des mots. Vous avez juste à trier la bonne chose; les personnages, pas les mots.
- Quelle langue ciblez-vous?
- Je suis évidemment heureux d'avoir ma réponse non acceptée pour un plus agréable solution, mais auriez-vous l'esprit jusqu'à droit de vote si vous le mais il s'est avéré utile? Merci!
- Ouais, bien sûr bro.Merci !
Vous devez vous connecter pour publier un commentaire.
La solution évidente est de cartographier chaque personnage a un nombre premier et multiplier les nombres premiers. Donc, si "a" -> 2 et 'b' -> 3, puis
Afin de minimiser les risques de débordement, le plus petit des nombres premiers peut être attribué à la plus fréquente des lettres (e,t,i,a,n). Remarque: Le 26 premier est de 101.
Mise à JOUR:
une mise en œuvre peut être trouvé ici
Une fonction de hachage peut être (en supposant que les mots en anglais seulement) un classement de compter le nombre d'occurrences de chaque lettre. Donc, pour "anagramme" vous devez générer [('a', 3), ('g', 1), ('n', 1), ('m', 1), ('r',1)].
Sinon, vous pourriez obtenir une inexact de regroupement par la génération d'un masque de bits à partir de votre mot où, pour les bits de 0 à 25 chaque bit a représenté la présence ou l'absence de cette lettre (bit 0 représentant de " a " à peu 25 representining 'z'). Mais alors que vous auriez à faire un peu plus de traitement de diviser chaque haché groupe de distinguer par exemple "de" de "en trop".
Effectuer une de ces idées vous aider? Tout particulier de la mise en œuvre de la langue à l'esprit (je pouvais faire, C++, python ou Scala)?
Edit: ajout d'un exemple de code Scala et de sortie:
OK: je suis dans le Scala mode en ce moment, alors j'ai frappé quelque chose à faire ce que vous demandez, mais (ahem), il peut ne pas être très clair, si vous n'êtes pas familier avec Scala ou de la programmation fonctionnelle.
À l'aide d'une grande liste de mots anglais à partir d'ici: http://scrapmaker.com/data/wordlists/twelve-dicts/2of12.txt
J'exécute ce code Scala sur eux (environ 5 secondes à l'aide de la Scala de 2,9 en mode script, y compris le temps de compiler, avec un dictionnaire de près de 40 000 mots. Pas le code le plus efficace, mais la première chose qui vient à l'esprit).
Cette déverse les 10 premiers jeux d'anagrammes (avec des ensembles de la plupart des membres de la première) en cours:
Remarque que cela utilise la première suggestion (liste des comtes de lettres) pas le plus compliqué masque de méthode.
Edit 2: Vous pouvez remplacer la fonction de hachage avec un simple tri sur les caractères de chaque mot (comme suggéré par la commission paritaire de recours) et obtenir le même résultat avec plus clair/plus rapide code:
Si vous XOR le hash-code de valeurs de chaque personnage, et puis XOR le résultat par le nombre d'entrées longueur, vous obtiendrez la même valeur quel que soit l'ordre de la parole, ce qui signifie que toutes les anagrammes produira le même hash. (XORing par la longueur empêche de "patron" et " bo " de retourner la même valeur, car la valeur de hachage de la 's' contre lui-même est toujours 0.)
Exemple:
Vous aurez toujours à la recherche de tous les mots avec la même AnagramHash. Je voudrais mettre à jour le dictionnaire de la table avec un champ pour la valeur de hachage (indépendamment de votre algorithme) permettant une réduction de calcul.
EDIT:
Aussi, comme une note de côté, XOR est la plus simple opération effectuée par l'ALU donc si vous ne les utilisez en fin de compte, vous devriez être en mesure de générer votre hachages assez rapidement.
GetHashCode()
est une méthode sur toutes les classes. Essentiellement, il génère un entier unique valeur de tout objet. (Les objets ayant la même valeur produira le même entier.) Pour une autre langue, vous pouvez simplement utiliser la valeur de l'octet de chaque personnage, comme le code de hachage, parce qu'ils seraient toujours être unique pour chaque valeur.AnagramHash
.L'échange de temps de la complexité de la mémoire supplémentaire, simplement pour stocker le nombre de lettres dans un mot (26
char
(ou l'équivalent dans la langue que vous utilisez, et en supposant que vous êtes en utilisant l'alphabet Romain et seulement des caractères alphabétiques) tableau de hachage et de la matrice. Vous êtes coincé avec O(n) fois par rapport à la longueur des mots, mais la plupart des mots anglais ne sont pas vraiment longtemps.par exemple
stack
,sackt
, etstakc
aimerait tous avoir un tableau avec les emplacements pours
,t
,a
,c
,k
== 1 et le reste tous ensemble à 0.En fonction de votre commentaire, ce qui implique que vous êtes bien d'accord avec tri les caractères d'un mot, tant que vous n'êtes pas le tri des mots eux-mêmes, vous pourriez faire quelque chose d'encore plus simple que de Alex de la réponse et juste trier les caractères dans le mot de chaînes de hachage et les résultats. (larsmans dit le premier, mais je n'ai pas poster comme une réponse, donc...)
Utiliser une table de hachage avec de la ficelle comme la clé et de la liste(string) as de la valeur là où liste de chaînes de caractères contiennent tous les anagrammes d'une chaîne de clé.
La question est similaire à "trouver tous les anagrammes d'un mot dans un fichier"
Vue algo et le code ici http://justprogrammng.blogspot.com/2012/06/determine-anagrams-of-word-in-file.html