Generieren Sie alle möglichen Buchstabenkombinationen in einem Wort

Ich werde meinen Hut mit der iterativen Version der Heap-Methode zum Generieren von Permutationen in den Ring werfen. Es hat eine Weile gedauert, bis ich richtig lag, da meine Referenzquelle einen Tippfehler im Algorithmus -_- hat.

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; } 

Mit einigen Beispiel-Timings zum Zählen der Anagramme von „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 

Kommentare

• Dies ist bei weitem der Gewinner, der 3.628.800 Ergebnisse in ~ 5.000 ms!
• Schön! Sie sollten die Array-Größen vorberechnen, um wahrscheinlich noch bessere Ergebnisse zu erzielen (da Anagramme und Zähler massive Arrays sind). Ich denke, ich werde versuchen, einen verteilten Ansatz zu wählen, um diesen zu schlagen 🙂
• Es ist ‚ interessant, wie dies mit Eingaben unterschiedlicher Größe skaliert wird jsperf.com/getanagramsc-r/2
• @megawac Es würde mich interessieren, Ihren Ansatz zu sehen, nachdem Sie die Stärken dieses Ansatzes genutzt haben.

Als ich an einer besseren Lösung arbeitete, fand ich eine großartige Verwendung für die neue JS-Iteratoren & Generatoren , über die ich gelesen habe. Ich habe heute wahrscheinlich 6 Stunden damit verbracht, an dieser Lösung herumzuspielen, und das war es auch jede Minute wert. Sie haben einige Formatierungsfehler, aber Ich werde mich ganz auf die Leistung konzentrieren und die Formatierung verlassen an die anderen Rezensenten.

Wenn Sie dies gegen ein großes Wort ausführen, wird Ihre Maschine braten.

Ok, vielleicht geht das auch ein bisschen weit, aber Im Ernst, Dies ist eine teure Funktion. Ich bin kein Mathe-Guru, also Ich habe diese Frage zu Math.SE gestellt .

Die Formel zur Berechnung der Anzahl möglicher Kombinationen ist extrem steil:

Stellen Sie sich das so vor:

Wie viele Möglichkeiten haben Sie für den ersten Buchstaben? Vier: 4_ _ _ _.

Zum zweiten? Drei: 4⋅3 _ _.

Fahren Sie so fort und Sie finden, dass es insgesamt 4⋅3⋅2⋅1 = 4! = 24 Auswahlmöglichkeiten gibt. – MrRicci

Führen Sie Ihre Funktion gegen das Wort aus „Encyclopedia“ führt zu einem eindeutigen Seitenabsturz, wenn Sie es clientseitig ausführen. Um das zu beheben, habe ich mir einige Gedanken gemacht.

Nehmen Sie mit – Dies wird beim Lesen immer relevanter.

Ich wollte versuchen, echte Wörter zu generieren (Spaß mit dem Codez haben)

An Anagramm ist eine Art Wortspiel, das Ergebnis der Neuanordnung der Buchstaben eines Wortes oder einer Phrase, um ein neues Wort oder eine neue Phrase zu erzeugen, wobei alle Originalbuchstaben genau einmal verwendet werden – Wikipeda

Wenn ich an ein Anagramm denke, denke ich, dass das Ergebnis echte Wörter oder Phrasen sind. Obwohl der Zweck dieser Codeüberprüfung nicht darin besteht, die Funktionalität Ihres Codes zu ändern, konnte ich nicht anders, als Spaß daran zu haben. Deshalb habe ich mich entschlossen, nach einer Lösung zu suchen, mit der ich alle echten Wortanagramme aus dem Ergebnis herausfiltern und ausdrucken kann.

Nachdem ich endlich eine einfache Textzeichenfolge von ~ 130.000 englische Wörter , um sie als meine Wortliste zu verwenden, musste ich diese Liste dann in JS konvertieren.Deshalb habe ich eine Funktion erstellt, um die Zeichenfolge in jedes Leerzeichen zu schneiden und die Struktur für ein Objekt mit Schlüsseleigenschaften auszudrucken, sodass ich über worldList["word"] -> returns true if word is valid.

Das Ausdrucken einer Liste mit 130.000 Wörtern als JSON-Zeichenfolge in den Dokumententext ist wie Ihre Funktion sehr teuer.

… und die Relevanz:

Hier trifft Ihr Problem also auf das, das ich für mich selbst erfunden habe. Wie verarbeiten Sie a Sehr teure Schleife ohne Absturz einer Webseite?

Beim Experimentieren mit den Möglichkeiten habe ich tatsächlich einen Weg gefunden, meine Funktion zuzulassen Behandeln Sie 130.000 Wörter und Ihre Funktion, um ein Wort beliebiger Größe aufrechtzuerhalten, indem Sie die Arbeitslast über die Zeit ausgleichen.

Schleifen sind manchmal zu schnell zu ihrem eigenen Besten

Schleifen sind so schnell wie möglich, was für die meisten perfekt ist der Aufgaben, für die wir sie in Webseiten verwenden. Wenn wir sie jedoch bitten, zu viel zu verarbeiten, kann der Browser nicht damit umgehen.

Ich brauchte also eine Lösung, mit der ich die Arbeitslast über die Zeit verteilen kann, damit die Seite verarbeitet werden kann teure Schleifen ohne Probleme.

Meine Lösung bestand darin, eine manuelle Schleife über eine Funktion zu erstellen, die sich x mal aufrief und 1-2ms Verzögerung zwischen Iterationen. Dies gab der Seite genügend Zeit, um die Schleife zu verarbeiten, die ohne Verzögerung Wörter verarbeitete wahnsinnig schnell bis zum C „s vor jedem Absturz. Dies funktionierte hervorragend zum Generieren meiner JSON-Wortlistenstruktur.

Die Implementierung einer verzögerten Schleife in Ihrer bereits rekursiven Funktion war jedoch äußerst schwierig.

Ich erkannte dann, dass dies die perfekte Situation ist, um eine Lösung zu verwenden, über die ich kürzlich für JavaScript gelesen habe …

JavaScript-Iteratoren und -Generatoren

Hier kommen also JavaScript-Iteratoren & Generatoren zur Rettung.

Nun, diese Rezension ist bereits ein Risiko, ein Monster zu werden. Anstatt Generatoren zu erklären, werde ich zitieren, um bald eine beliebte Antwort zu sein „s Einzeiler:

TL; DR: Das Wesentliche bei der Verwendung eines Generators ist die Steuerung der Unterbrechung der Codeausführung.

Und erklären Sie einfach, dass Generatoren Iteratoren besser implementieren können.

Den Rest können Sie in der Antwort dort selbst lesen. Wenn diese Antwort nicht ganz für Sie geeignet ist, können Sie Ihr Verständnis über die folgenden Ressourcen verbessern:

• Javascript „s Zukunft: Generatoren

• Generatoren: eine bessere Möglichkeit, Iteratoren zu erstellen

• Generatoren – MDN

• Was nennt das Generatoren?

Jetzt haben Generatoren ein großes Potenzial bei der Vermeidung der Rückrufhölle, aber wir werden es tun Verwenden Sie sie hier nicht zum Formatieren der & -Struktur, sondern für die Leistung, die (meiner Meinung nach leistungsabhängig) der eleganteste Grund ist, sie zu verwenden.

Ich bin mir noch nicht sicher, ob die Generatoren hier die beste Lösung sind, aber sie sind die beste Idee, die ich habe, und das hier ist eine Ausrede, um sie auszuprobieren.

Ihr Code mit Generatoren

Arbeiten an diese Lösung noch. Es sollte gut funktionieren, ich habe noch keine Zeit, um fertig zu werden, und wollte den verbesserten Code eher früher als später anbieten. Ich werde diese Lösung bald veröffentlichen.

Update: Ein paar Tage Später habe ich das Erlernen von Generatoren noch nicht abgeschlossen, bis ich diese Funktion korrekt mit ihnen schreiben kann. Ich werde sie definitiv hier veröffentlichen, sobald ich ihre Syntax ein wenig besser herausgefunden habe.

Und schließlich, da Generatoren neu sind und noch nicht überall unterstützt werden. Eine verbesserte Version Ihres Codes ohne sie

Hinweis: Meine Formatierungspraktiken sind im Allgemeinen meine eigene Lesbarkeit Präferenz statt Best Practice. Fühlen Sie sich nicht verpflichtet, Ihren Code auf diese Weise zu formatieren.

/* 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); 

Durch die Deklaration von Variablen außerhalb der Schleifen sparen wir erheblich Sie werden es in den Ergebnissen sehen. Ich glaube auch, dass word.slice() etwas besser abschneidet als word.substr() zwischen diesen beiden Optimierungen, diesem Code führt sein tter als Ihr ursprünglicher Code.

Und nicht zuletzt die Leistungsergebnisse!

Originalcode : Ergebnisse aktualisiert! Seite stürzt nicht ohne Protokollierung ab.

• „Code“, 4 Zeichen: 24 Ergebnisse , ~ 1 ms
• „Codierer“, 5 Zeichen: 120 Ergebnisse , ~ 1 ms
• „codere“, 6 Zeichen: 720 Ergebnisse , ~ 6 ms
• „coderev“, 7 Zeichen: 5040 Ergebnisse , ~ 11 ms
• „coderevi“, 8 Zeichen: 40.320 Ergebnisse , ~ 75 ms
• „coderevie“, 9 Zeichen: 362.880 Ergebnisse , Seitenfehler
• „codereview“, 10 Zeichen: 3.628.800 Ergebnisse , Seite fehlgeschlagen

Verbesserter Code : Ergebnisse aktualisiert – Seite stürzt nicht ohne Protokollierung ab.

• “ Code „, 4 Zeichen: 24 Ergebnisse , ~ 0,5 ms
• “ Codierer „, 5 Zeichen: 120 Ergebnisse , ~ 0,5 ms
• „codere“, 6 Zeichen: 720 Ergebnisse , ~ 1,5 ms
• „coderev“, 7 Zeichen: 5040 Ergebnisse , ~ 8 ms
• “ coderevi „, 8 Zeichen: 40.320 Ergebnisse , ~ 53 ms
• “ coderevie „, 9 Zeichen: 362.880 Ergebnisse , ~ 556 ms
• „codereview“, 10 Zeichen: 3.628.800 Ergebnisse , ~ 12725 ms

Echtzeit mit Generatoren

(Code nicht vollständig – Generatoren erweisen sich als etwas schwierig)

Ich habe console.time(), um auf die nächste Millisekunde genaue Messungen zu erzielen, jeweils 3-5 Versuche abzuschließen und einen allgemeinen Durchschnitt basierend auf dem r zu schätzen Ergebnisse. Diese Ergebnisse variieren natürlich von Maschine zu Maschine. Die Zeitvergleiche sind der Schlüssel zum Lesen von Benchmarks, nicht die Geschwindigkeiten.

Tl; Dr. Zusammenfassung, wie versprochen

Schleifen sind äußerst leistungsfähig Tool in der Programmierung, aber sie verarbeiten Monsterzahlen teurer Iterationen im Webbrowser nicht gut. Teure Schleifenfunktionen wie diese funktionieren jedoch perfekt, wenn Sie die Arbeitslast über die Zeit verteilen. Eine interessante Möglichkeit, dies zu tun, ist die Verwendung von JS-Generatoren , ein neues Spielzeug, das heute in Webshops erhältlich ist, aber nicht unbedingt auf den lokalen Märkten. Verwenden Sie es daher vorsichtig, bis JS 2.0 weiter verbreitet ist! Durch die Nutzung der Leistung von JS-Generatoren Wir können lang laufende teure Prozesse verwalten, ohne dass Leistungsprobleme auftreten.

Kommentare

• Hat Haben Sie jemals Generatoren herausgefunden?
• @megawac Ich habe viele Stunden damit verbracht, ohne genügend Anleitungen / Informationen / Tutorials, um wirklich herauszufinden, wie es geht. I ‚ habe ausgegeben so viel Zeit, wie ich seit diesem Beitrag jeden Tag frei habe, um sie zu studieren, aber … Ich lerne ‚ nicht schnell aus der Rohdokumentation. Kennen Sie gute Ressourcen für Generatoren und Iteratoren?
• Klingt nach einem guten Stackoverflow-Thread @ jt0dd
• Ich habe einen Löser für die Lokalzeitung ‚ s Durcheinander-Puzzle. Ich hatte eine Liste mit 600.000 Scrabble-Wörtern, die ich vorverarbeitet habe, um die Buchstaben in jedem Wort zu sortieren. Ich habe dann dasselbe für die Suchbuchstaben gemacht und versucht, Wörter zu finden. Es kann nach allen Wörtern zwischen 4 und 10 Buchstaben suchen, wenn 10 Buchstaben in Millisekunden angegeben werden. Die in beliebiger Reihenfolge eingegebenen Buchstaben ‚ throb ‚ führen zu ‚ bhort ‚, das direkt mit ‚ throb ‚ und ‚ verknüpft ist Brühe ‚, Sie müssen nicht jede Kombination ausprobieren. Wenn Sie beispielsweise nach Wörtern mit 4 Buchstaben und 5 Buchstaben suchen, gibt es nur 4 Kombinationen, wenn die Buchstaben sortiert sind, 120, wenn nicht.
• @ jt0dd Ich ‚ bin verwirrt über die Verwendung von word.length + 1 bei Verwendung von Slice. Können Sie das bitte erklären?

Ich habe mir den Code von @ jt0dd angesehen und mich gefragt, wie wir könnte noch einige Fälle behandeln. Ich werde Ihnen sagen, lassen Sie uns eine Cache-Ebene hinzufügen und die Längen der resultierenden Arrays vorberechnen!

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 “ Ich hoffe, die ganze Zeit war nicht umsonst …

Vorberechnete Hashs

• „code“, 4 Zeichen: 24 Ergebnisse , < = 1 ms
• „Codierer“, 5 Zeichen: 120 Ergebnisse , < = 1 ms
• „codere“, 6 Zeichen: 720 Ergebnisse , < = 1 ms
• „coderev“, 7 Zeichen: 5040 Ergebnisse , < = 3 ms
• “ coderevi „, 8 Zeichen: 40.320 Ergebnisse , < = 18 ms
• „coderevie“, 9 Zeichen: 362.880 Ergebnisse , 135 ms
• „codereview“, 10 Zeichen: 3.628.800 Ergebnisse , 2,1 s

Whoopy, wir haben uns der Herausforderung gestellt. Mal sehen, wie weit wir noch gehen können. codereview ist ein hartes Wort, das nur e Zeichen dupliziert. Versuchen wir es für das nächste Mal einfacher Versuchen wir es mit "anagramarmy"

… … …

Okay, ich habe mehr abgebissen, als mein Browser kauen kann Es scheint, dass 40 Millionen String-Permutationen jenseits des Limits liegen 🙁

Sie werden feststellen, dass ich den Algorithmus neu gestaltet habe, um einen Stapelüberlauf zu vermeiden – Lookups sollten außerhalb der Rekursion durchgeführt werden.

Wir können die Wahrscheinlichkeit erhöhen, dass unser Algorithmus nicht abstürzt, indem wir ihn asynchron machen und alle Millisekunden 100,000 -Elemente ausführen, um ein Anhalten zu vermeiden.

Kommentare

• Super! Dies ist viel besser als die Generatorversion, an der ich ‚ arbeite. +1 ( Diese Antwort sollte akzeptiert werden. ‚ wird bei weitem effizienter sein als meine Generatorlösung.)
• Genial … Einfach genial. Ich wirklich so was. Wenn ich die Echtzeit-Harmony-Generator-Lösung fertiggestellt habe (oder Sie können Ihre eigene implementieren), können Sie dies gerne tun und dasselbe damit tun. Es ‚ wird langsamer sein, aber die Ergebnisse werden in Echtzeit zurückgegeben und haben kein Ende damit, wie groß ein Wort sein kann.
• ahh, mjolka hat uns geschlagen beide von far .
• Hallo, wie führe ich diesen Code neben HTML und CSS in meiner Domain aus? Ich ‚ benutze dieses kostenlose: morsetovoynich.000webhostapp.com

Ich habe zwei Skripte erstellt:

1. Das erste ist schnell, kann aber nicht viel halten;
2. Die zweite ist langsam, kann aber unbegrenzte Ergebnisse zeigen.

Beide verwenden den von mir erstellten Prototyp: fastPush, fastSplit und fastJoin, die schneller sind als die Standardmethode split and join. Beide auch Verwenden Sie bitweise, um zu überprüfen, ob ungerade oder gerade, da ich weiß, dass Mod die langsamste Operation ist, die auf einem Computer möglich ist.

Das erste Skript übertrifft das schnellste Ergebnis anderer um mehr als 750 ms (im Durchschnitt) bei einer 10-Gramm-Herausforderung der Permutation

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()); 

Auf jeden Fall hat dieses erste Programm ein Limit und bricht die Seite, wenn Sie mehr als 10 Zeichen versuchen.

Das zweite Programm (das eins unten) verwendet eine selbstaufrufende Funktion und meldet sich bei den Konsolenblöcken von 4e4-Elementen an, löscht das Anagramm-Array jedes Mal, wenn es einen Block ausgibt, und löscht auch co nsole.log jeweils 5 Chunks (genug, damit Sie diese Kombinationen sehen können). Um die Funktion selbst aufzurufen, verwendet das Programm setZeroTimeout ( David Barons Blog ) anstelle von setTimeout, da setTimeout viel langsamer ist.

(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"); 

Noch eine Variante (geschrieben in i C) mit einem einfachen Zähler über Power Set aller Zeichenfolgen.

#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); } 

Mit Druck aller Zeichenfolgen ausführen:

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

Kommentare

• Was meinen Sie mit “ Druck aller Zeichenfolgen „? Ihre Funktion gibt nur Teile des Wortes aus, z. B. wenn run` anagrams abc` a,b,ab,c,ac,bc,abc

Antwort

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

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

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; } 

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