Générer toutes les combinaisons possibles de lettres dans un mot

 function allAnagrams (word) { if (word.length < 2) { return [word]; } else { var allAnswers = []; for (var i = 0; i < word.length; i++) { var letter = word[i]; var shorterWord = word.substr(0, i) + word.substr(i + 1, word.length - 1); var shortwordArray = allAnagrams(shorterWord); for (var j = 0; j < shortwordArray.length; j++) { allAnswers.push(letter + shortwordArray[j]); } } return allAnswers; } } allAnagrams("") 

Je « vais jeter mon chapeau dans le ring avec la version itérative de la méthode de Heap » de génération de permutations. Il ma fallu un certain temps pour bien faire, car ma source de référence contient une faute de frappe dans lalgorithme -_-.

function swap(chars, i, j) { var tmp = chars[i]; chars[i] = chars[j]; chars[j] = tmp; } function getAnagrams(input) { var counter = [], anagrams = [], chars = input.split(""), length = chars.length, i; for (i = 0; i < length; i++) { counter[i] = 0; } anagrams.push(input); i = 0; while (i < length) { if (counter[i] < i) { swap(chars, i % 2 === 1 ? counter[i] : 0, i); counter[i]++; i = 0; anagrams.push(chars.join("")); } else { counter[i] = 0; i++; } } return anagrams; } 

Avec quelques exemples de temps pour compter les anagrammes de « codereview »:

$ time node anagrams-heap-iterative.js 3628800 real 0m0.855s user 0m0.000s sys 0m0.015s $ time node anagrams-megawac.js 3628800 real 0m2.286s user 0m0.000s sys 0m0.000s 

Commentaires

• Cest de loin le gagnant, calculant 3 628 800 résultats en ~5 000ms !
• Bien! Vous devriez précalculer la taille des tableaux pour obtenir des résultats encore meilleurs (car les anagrammes et les compteurs sont des tableaux massifs). Je pense que je vais essayer de devoir adopter une approche distribuée pour battre celui-ci 🙂
• Il ‘ est intéressant de voir comment cela évolue avec des entrées de taille différente jsperf.com/getanagramsc-r/2
• @megawac Je serais intéressé de voir votre approche après avoir utilisé les points forts de cette approche.

En travaillant sur une meilleure solution, jai trouvé une excellente utilisation du nouveau JS Iterators & Generators , que jai lu. Jai passé probablement 6 heures aujourdhui à manipuler cette solution, et cétait vaut chaque minute. Vous avez des erreurs de formatage, mais Je vais me concentrer entièrement sur les performances et laisser le formatage aux autres réviseurs.

---

Exécuter ceci contre un grand mot fera frire votre machine

Ok, alors peut-être que cela va peu aussi loin, mais sérieusement, cest une fonction coûteuse. Je « ne suis pas un gourou des mathématiques, donc Jai posé cette question sur Math.SE .

La formule pour calculer le nombre de combinaisons possibles est extrêmement raide:

Pensez-y comme ceci:

Combien de choix avez-vous pour la première lettre? Quatre: 4_ _ _ _.

Pour la seconde? Trois: 4⋅3 _ _.

Continuez ainsi et vous trouverez quil y a 4⋅3⋅2⋅1 = 4! = 24 choix au total. – MrRicci

Exécution de votre fonction contre le mot « Encyclopédie » entraînera un plantage définitif de la page si vous lexécutez côté client. Donc, pour résoudre ce problème, jai réfléchi.

---

Restez avec moi – Cela devient de plus en plus pertinent au fur et à mesure que vous lisez.

Je voulais essayer de générer de vrais mots (Samuser avec le codez)

Un anagramme est un type de jeu de mots, le résultat de la réorganisation des lettres dun mot ou dune phrase pour produire un nouveau mot ou une nouvelle phrase, en utilisant toutes les lettres originales exactement une fois – Wikipeda

Quand je pense à un anagramme, je pense que le résultat est des mots ou des phrases réels . Maintenant, alors que le but de cette revue de code nest pas de changer la fonctionnalité de votre code, je ne pourrais pas mempêcher de vouloir mamuser avec. Jai donc décidé de rechercher une solution qui me permettrait de filtrer et dimprimer tous les anagrammes de mots réels du résultat.

Une fois, jai finalement retrouvé une chaîne de texte brut de ~ 130 000 mots anglais à utiliser comme liste de mots, jai ensuite dû convertir cette liste en JS.Jai donc créé une fonction pour découper la chaîne à chaque espace et imprimer la structure dun objet avec des propriétés clés, afin de pouvoir très rapidement tester la validité de nimporte quel mot via worldList["word"] -> returns true if word is valid.

Imprimer une liste de 130 000 mots dans le corps du document sous forme de chaîne JSON est, comme votre fonction, très coûteux.

---

… Et la pertinence:

Voici donc où votre problème rencontre celui que jai inventé pour moi-même. Comment traitez-vous un boucle très coûteuse sans planter une page Web?

En expérimentant les possibilités, jai en fait découvert un moyen de permettre à ma fonction de gérer 130 000 mots, et votre fonction pour soutenir un mot de nimporte quelle taille , en équilibrant la charge de travail au fil du temps.

Les boucles sont parfois trop rapides pour leur propre bien

Les boucles sont conçues pour être aussi rapides que possible, ce qui est parfait pour la plupart des tâches pour lesquelles nous les utilisons dans les pages Web. Mais si on leur demande de gérer trop de choses, le navigateur ne peut pas le gérer.

Javais donc besoin dune solution qui me permettrait de répartir la charge de travail dans le temps, afin de permettre à la page de gérer boucles coûteuses sans problème.

Ma solution était de construire une boucle manuelle via une fonction qui sappelait x fois, en insérant un 1-2ms délai entre les itérations. Cela a donné à la page suffisamment de temps pour gérer la boucle , qui, sans délai, traitait les mots incroyablement rapide jusquaux C avant de sécraser à chaque fois. Cela a très bien fonctionné pour générer ma structure de liste de mots JSON.

Mais une boucle retardée était extrêmement délicate à implémenter dans votre fonction déjà récursive.

Jai alors réalisé que cétait la situation idéale pour utiliser une solution que jai récemment lue pour JavaScript …

---

Itérateurs et générateurs JavaScript

Alors, voici les itérateurs JavaScript & Générateurs à la rescousse.

Maintenant, cette critique risque déjà de devenir un monstre, donc au lieu dexpliquer Generators, je vais citer cette réponse bientôt populaire « s one-liner:

TL; DR: lessence de [lutilisation dun] générateur est de contrôler la suspension de lexécution du code.

Et expliquez simplement que les générateurs sont dune manière améliorée dimplémenter des itérateurs.

Vous pouvez lire le reste par vous-même dans la réponse. Si cette réponse ne vous convient pas, vous pouvez améliorer votre compréhension grâce aux ressources suivantes:

• Javascript « s Avenir: Générateurs

• Générateurs: une meilleure façon de créer des itérateurs

• Générateurs – MDN

• Quest-ce que cette chose appelée générateurs?

Maintenant, les générateurs ont un grand potentiel pour éviter lenfer des rappels, mais nous allons les utiliser ici non pas pour le formatage de la structure &, mais pour les performances, ce qui est (à mon avis, axé sur les performances) la raison la plus élégante de les utiliser.

Je ne sais pas encore si les générateurs sont la meilleure solution ici, mais ils « sont la meilleure idée que jai, et ceci est une excuse pour les essayer.

---

Votre code avec des générateurs

Travailler sur cette solution encore. Cela devrait très bien fonctionner, je nai pas encore le temps de terminer, et je voulais proposer le code amélioré le plus tôt possible. Je publierai cette solution bientôt.

Mise à jour: quelques jours plus tard, je nai pas fini dapprendre les générateurs, au point de pouvoir écrire correctement cette fonction avec eux. Je la posterai certainement ici dès que jaurai un peu mieux compris leur syntaxe.

---

Et enfin, puisque les générateurs sont nouveaux et pas encore pris en charge partout .. Une version améliorée de votre code sans eux

Remarque: Mes pratiques de mise en forme sont généralement ma propre lisibilité préférence plutôt que la meilleure pratique. Ne vous sentez pas obligé de formater votre code de cette façon.

/* Improved Real Time Anagram Engine */ // Without generators, it"s difficult to write this function // with the capability of processing a word of any length without // crashing the web browser, so this is written as the original, // with non-controlled execution speed. Long (9+ char) words may // crash browser. function generateAnagrams(word) { if (word.length < 2) { return [word]; } else { // By declaring all variables outside of the loop, // we improve efficiency, avoiding the needless // declarations each time. var anagrams = []; var before, focus, after; var shortWord, subAnagrams, newEntry; for (var i = 0; i < word.length; i++) { before = word.slice(0, i); focus = word[i]; after = word.slice(i + 1, word.length + 1); shortWord = before + after; subAnagrams = generateAnagrams(shortWord); for (var j = 0; j < subAnagrams.length; j++){ newEntry = focus + subAnagrams[j]; anagrams.push(newEntry); } } return anagrams; } } var result = generateAnagrams(word); 

En déclarant des variables en dehors des boucles, nous économisons de manière significative, comme vous « verrez dans les résultats. De plus, je crois que word.slice() a légèrement mieux performé que word.substr(). Entre les deux de ces optimisations, ce code effectue être tter que votre code dorigine.

---

Et le dernier mais pas le moindre, les résultats des performances!

Code dorigine : résultats mis à jour! La page ne plante pas sans journalisation.

• « code », 4 caractères: 24 résultats , ~ 1 ms
• « coder », 5 caractères: 120 résultats , ~ 1ms
• « codere », 6 caractères: 720 résultats , ~ 6ms
• « coderev », 7 caractères: 5040 résultats , ~ 11 ms
• « coderevi », 8 caractères: 40 320 résultats , ~ 75 ms
• « coderevie », 9 caractères: 362 880 résultats , échec de la page
• « codereview », 10 caractères: 3 628 800 résultats , échec de la page

Code amélioré : Résultats mis à jour – La page ne plante pas sans journalisation.

•  » code « , 4 caractères: 24 résultats , ~ 0,5 ms
•  » coder « , 5 caractères: 120 résultats , ~ 0,5 ms
• « codere », 6 caractères: 720 résultats , ~ 1,5 ms
• « coderev », 7 caractères: 5040 résultats , ~ 8 ms
•  » coderevi « , 8 caractères: 40,320 résultats , ~ 53 ms
•  » coderevie « , 9 caractères: 362 880 résultats , ~ 556 ms
• « codereview », 10 caractères: 3 628 800 résultats , ~ 12725 ms

Temps réel avec générateurs

(Code incomplet – Les générateurs savèrent un peu difficiles)

Jai utilisé console.time() pour obtenir des mesures précises à la milliseconde près, en effectuant 3 à 5 essais chacun et en estimant une moyenne générale basée sur le r résultats. Ces résultats varieront bien entendu dune machine à lautre. Les comparaisons de temps sont la clé pour lire les benchmarks, pas les vitesses.

---

Tl; Dr Summary, comme promis

Les boucles sont extrêmement puissantes outil de programmation, mais ils ne gèrent pas bien un nombre impressionnant ditérations coûteuses dans le navigateur Web. Des fonctions de bouclage coûteuses comme celle-ci fonctionnent parfaitement, cependant, si vous répartissez la charge de travail dans le temps. Une façon intéressante de le faire est dutiliser des générateurs JS , un nouveau jouet disponible dans les boutiques en ligne aujourdhui, mais pas nécessairement sur les marchés locaux, alors utilisez-le avec précaution jusquà ce que JS 2.0 soit plus largement implémenté! En utilisant la puissance des générateurs JS, nous pouvons gérer des processus coûteux de longue durée sans rencontrer de problèmes de performances.

Commentaires

• Fait avez-vous déjà découvert des générateurs?
• @megawac Jai passé de nombreuses heures dessus, sans suffisamment de guides / informations / tutoriels pour vraiment comprendre comment le faire. I ‘ ai dépensé autant de temps que je dispose chaque jour depuis ce post pour les étudier, mais … je ne ‘ pas apprendre rapidement de la documentation brute. Connaissez-vous de bonnes ressources sur les générateurs et les itérateurs?
• Sonne comme un bon thread stackoverflow @ jt0dd
• Jai écrit un solveur pour le journal local ‘. Javais une liste de 600 000 mots de scrabble que jai prétraités pour trier les lettres de chaque mot. Jai ensuite fait la même chose pour les lettres de recherche et jai essayé de trouver des mots. Il peut rechercher tous les mots entre 4 et 10 lettres, avec 10 lettres en millisecondes. Les lettres ‘ throb ‘ saisies dans nimporte quel ordre aboutissent à ‘ bhort ‘ qui renvoie directement à ‘ throb ‘ et ‘ bouillon ‘, pas besoin dessayer toutes les combinaisons. Par exemple, si vous recherchez des mots de 4 lettres avec 5 lettres, il ny a que 4 combinaisons lorsque les lettres sont triées, 120 sinon.
• @ jt0dd I ‘ m confus à propos de lutilisation de word.length + 1 lors de lutilisation de slice. Pouvez-vous expliquer?

Jai jeté un coup dœil au code de @ jt0dd et je me suis demandé comment nous pourrait gérer dautres cas. Je « vais vous dire, ajoutons une couche de cache et précalculons les longueurs des tableaux résultants!

var generateAnagrams = (function() { // precomputed first 20 factorials var fact20 = [1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 6227020800, 87178291200, 1307674368000, 20922789888000, 355687428096000, 6402373705728000, 121645100408832000, 2432902008176640000]; // Substrings seen already which we can cache. Try and avoid stack overflow as much as possible var seenStrings = {}; function generateAnagrams(word) { var length = word.length; if (length < 2) { seenStrings[word] = word; return [word]; } var anagrams = Array(fact20[length - 1]); // Stuff we"ll need along the way var before, focus, after; var shortWord, subAnagrams, newEntry; var idx = 0, j, jlen; for (var i = 0; i < length; i++) { before = word.slice(0, i); focus = word[i]; after = word.slice(i + 1, word.length + 1); shortWord = before + after; subAnagrams = seenStrings[shortWord] || generateAnagrams(shortWord); for (j = 0, jlen = subAnagrams.length; j < jlen; j++) { newEntry = focus + subAnagrams[j]; anagrams[idx++] = newEntry; } } seenStrings[word] = anagrams; return anagrams; } return function anagrams(word) { var computed = generateAnagrams(word); // clear cache (going to consume a ton of memory) seenStrings = {}; return computed; }; })(); 

Man that » Jespère que tout ce temps na pas été pour rien …

Hashs pré-calculés

• « code », 4 caractères: 24 résultats , < = 1ms
• « coder », 5 caractères: 120 résultats , < = 1ms
• « codere », 6 caractères: 720 résultats , < = 1ms
• « coderev », 7 caractères: 5040 résultats , < = 3ms
•  » coderevi « , 8 caractères: 40 320 résultats , < = 18ms
• « coderevie », 9 caractères: 362 880 résultats , 135 ms
• « codereview », 10 caractères: 3 628 800 résultats , 2,1 s

Whoopy, nous avons relevé le défi. Voyons jusquoù nous pouvons aller. codereview est un mot dur ne duplique que les e caractères. Essayons quelque chose de plus simple pour le suivant Allez. Essayons "anagramarmy"

… … …

Daccord, jai mordu plus que mon navigateur ne peut mâcher il semble que 40 millions de permutations de chaînes semblent être au-delà de la limite: (

Vous remarquerez que jai repensé lalgorithme pour éviter le débordement de la pile – les recherches doivent être effectuées en dehors de la récursivité.

Nous pouvons augmenter les chances que notre algorithme ne plante pas en le rendant asynchrone et en faisant tous les éléments 100,000 toutes les millisecondes pour éviter de sarrêter.

Commentaires

• Génial! Cest bien mieux que la version du générateur sur laquelle ‘ travaille. +1 ( Cette réponse doit être acceptée, elle ‘ va être de loin plus efficace que ma solution de générateur.)
• Brillant … Juste génial. Je vraiment comme ça. Lorsque jai terminé la solution du générateur dharmonie en temps réel (ou que vous pouvez implémenter la vôtre), nhésitez pas à prendre cela et à faire de même avec. Cela ‘ sera plus lent, mais retournera les résultats en temps réel et naura pas de limite à la taille dun mot quil peut gérer.
• ahh, mjolka nous bat les deux par far .
• Salut, comment puis-je exécuter ce code avec html et css dans mon domaine? Jutilise ‘ celui-ci gratuit: morsetovoynich.000webhostapp.com

Jai fait deux scripts:

1. Le premier est rapide mais ne peut « pas tenir grand chose;
2. La seconde est lente mais peut montrer des résultats illimités.

Les deux utilisent le prototype que jai fait: fastPush, fastSplit et fastJoin; qui sont plus rapides que la méthode standard split and join. Les deux aussi utilisez bitwise pour vérifier si impair ou pair, car je sais que le mod est lopération la plus lente possible sur un ordinateur.

Le premier script bat le résultat le plus rapide des autres de plus de 750 ms (en moyenne) sur un défi de permutation de 10 caractères .

Array.prototype.swap = function(i, j) { var el1 = this[i], el2 = this[j]; this[i] = el2; this[j] = el1; return this; }; Array.prototype.fastPush = function(element) { this[this.length] = element; }; String.prototype.fastSplit = function() { var array = []; for(var i = 0; i < this.length; i++) array.fastPush(this[i]); return array; }; Array.prototype.fastJoin = function() { var string = ""; for(var i = 0; i < this.length; i++) string += this[i]; return string; }; String.prototype.anagrams = function() { var i = 1, N = this.length, p = [], anagrams = [], k, word = this.fastSplit(); anagrams.fastPush(this.toString()); for(var j = 0; j < N; j++) p.fastPush(0); while(i < N) { if(p[i] < i) { k = 0; k = (i & 1 != 0) & p[i]; anagrams.fastPush(word.swap(k, i).fastJoin()); p[i]++; i = 1; } else { p[i] = 0; i++ } } return anagrams; }; console.log("asdasdfghj".anagrams()); 

Quoi quil en soit, ce premier programme a une limite et casse la page si vous essayez plus de 10 caractères.

Le deuxième programme (le un ci-dessous) utilise une fonction auto-appelante et se connecte aux morceaux de console déléments 4e4, il efface le tableau danagrammes chaque fois quil génère un morceau et efface également co nsole.log chaque 5 morceaux (assez pour vous permettre de voir ces combinaisons). Pour invoquer automatiquement la fonction, le programme utilise setZeroTimeout ( blog de David Baron ) au lieu de setTimeout car setTimeout est beaucoup plus lent.

(function() { var timeouts = []; var messageName = "zero-timeout-message"; // Like setTimeout, but only takes a function argument. There"s // no time argument (always zero) and no arguments (you have to // use a closure). function setZeroTimeout(fn) { timeouts.fastPush(fn); window.postMessage(messageName, "*"); } function handleMessage(event) { if (event.source == window && event.data == messageName) { event.stopPropagation(); if (timeouts.length > 0) { var fn = timeouts.shift(); fn(); } } } window.addEventListener("message", handleMessage, true); // Add the one thing we want added to the window object. window.setZeroTimeout = setZeroTimeout; })(); Array.prototype.swap = function(i, j) { var el1 = this[i], el2 = this[j]; this[i] = el2; this[j] = el1; return this; }; Array.prototype.fastPush = function(element) { this[this.length] = element; }; String.prototype.fastSplit = function() { var array = []; for(var i = 0; i < this.length; i++) array.fastPush(this[i]); return array; }; Array.prototype.fastJoin = function() { var string = ""; for(var i = 0; i < this.length; i++) string += this[i]; return string; }; var i = 1, p = [], N, k, chars, anagrams = [], r = 0; function anagramsGen(word) { N = word.length; chars = word.fastSplit(); anagrams.fastPush(word); for(var j = 0; j < N; j++) p.fastPush(0); noLimitWhile(); } function noLimitWhile() { if(i < N) { if(p[i] < i) { k = 0; k = (i & 1 != 0) & p[i]; anagrams.fastPush(chars.swap(k, i).fastJoin()); if(anagrams.length === 4e4) { if(r === 5) { console.clear(); r = 0; } r++; console.log(anagrams); anagrams = []; } p[i]++; i = 1; } else { p[i] = 0; i++ } setZeroTimeout(noLimitWhile); } else { console.log(anagrams); console.log("Finished"); } } anagramsGen("qwertyuiopas"); 

Encore une autre variante (écrite en i C) utilisant un simple compteur sur Power Set de toutes les chaînes.

#include <string.h> #include <stdio.h> int main(int argc, char* argv[]) { if (argc < 2) return (1); char* arg = argv[1]; int n = 1 << strlen(arg); for (int i = 1; i < n; i++) { for (int j = 1, l = 0; j <= i; j <<= 1, l++) { if (i & j) printf("%c", arg[l]); } printf("\n"); } return (0); } 

Exécuter avec limpression de toutes les chaînes:

$ time anagrams codereview > log real 0m0.002s user 0m0.000s sys 0m0.000s 

Commentaires

• Quentendez-vous par  » impression de toutes les chaînes « ? Votre fonction ne produit que des parties du mot, par exemple si run` anagrams abc` renvoie a,b,ab,c,ac,bc,abc

Des tableaux typés pour de meilleures performances.

En utilisant la méthode des réponses acceptées, vous pouvez tripler les performances.

Lancer la réponse gagnante sur ma machine a donné un benchmark

Mean : 5,564,999µs ±182,246µs 11 samples 

Et lors de lutilisation de t tableaux yped

Mean : 1,514,112µs ±72,000µs (*) 13 samples 

pour une augmentation des performances de 3,68.

var knownPermutations = [0,0,0,24,120,720,5040,40320,362880,3628800]; function anagramer(input) { var counter, chars,length,i,index,tc,n,arraySize,anagrams; index = 0; length = input.length; arraySize = knownPermutations[length-1] * length; anagrams = new Uint8Array(arraySize); chars = new Uint8Array(length); counter = new Uint8Array(length); for( i = 0; i < length; i ++){ chars[i] = input.charCodeAt(i); } anagrams.set(chars) index += length; i = 0; while (i < length) { if (counter[i] < i) { tc = chars[i]; chars[i] = chars[n= (i%2?counter[i]:0)]; chars[n] = tc; counter[i]++; i = 0; anagrams.set(chars,index) index += length; } else { counter[i] = 0; i++; } } return anagrams; } 

Pour un peu plus vous pouvez prédéfinir le tableau de résultats pour obtenir

 Mean : 1,408,974µs ±25,173µs (*) 24 samples 

Pour laméliorer jusquà 3,95 fois plus vite que la réponse gagnante.