Generera alla möjliga bokstavskombinationer i ett ord

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

Jag ska kasta min hatt i ringen med den iterativa versionen av Heaps metod för att skapa permutationer. Det tog mig ett tag att komma rätt, eftersom min referenskälla har ett skrivfel i algoritmen -_-.

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

Med några provtider för att räkna anagrammen för ”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 

Kommentarer

• Detta är av långt vinnaren, beräknar 3 628 800 resultat inom ~5,000ms !
• Trevligt! Du borde förberäkna matrisstorlekarna kommer sannolikt att ge ännu större resultat (eftersom anagram och räknare är massiva matriser). Jag tror att jag kommer att försöka behöva ta ett distribuerat tillvägagångssätt för att slå den här 🙂
• Det ’ är intressant hur detta skalas med olika storleksingångar jsperf.com/getanagramsc-r/2
• @megawac Jag skulle vara intresserad av att se ditt tillvägagångssätt efter att ha använt styrkan i detta tillvägagångssätt.

När jag arbetade med en bättre lösning räknade jag ut en bra användning för den nya JS Iterators & Generatorer , som jag har läst om. Jag spenderade troligen 6 timmar idag med den här lösningen, och det var värt varje minut. Du har några formateringsfel, men Jag kommer att fokusera helt på prestanda och lämna formateringen till de andra granskarna.

---

Att köra detta mot ett stort ord kommer att steka din maskin

Okej, så det kanske går lite också långt, men på allvar, detta är en dyr funktion. Jag är ingen matematikguru, så Jag ställde den här frågan på Math.SE .

Formeln för att beräkna antalet möjliga kombinationer är extremt brant:

Tänk på det så här:

Hur många val har du för första bokstaven? Fyra: 4_ _ _ _.

För det andra? Tre: 4⋅3 _ _.

Fortsätt så här och du hittar att det finns 4⋅3⋅2⋅1 = 4! = 24 val totalt. – MrRicci

Kör din funktion mot ordet ”Encyclopedia” kommer att resultera i en definitiv sidkrasch om du kör den på klientsidan. Så för att fixa det tänkte jag lite.

---

Håll med mig – detta blir mer och mer relevant när du läser.

Jag ville prova att skapa riktiga ord (ha roligt med codez)

En anagram är en typ av ordspel, resultatet av att ordna om bokstäverna i ett ord eller en fras för att producera ett nytt ord eller en ny fras med alla originalbokstäverna exakt en gång – Wikipedia

När jag tänker på ett anagram tänker jag på att resultatet blir riktiga ord eller fraser. Medan syftet med den här kodgranskningen inte är att ändra din kods funktionalitet, kunde jag inte låta bli att ha kul med den. Så jag bestämde mig för att söka efter en lösning som gjorde det möjligt för mig att filtrera bort och skriva ut alla riktiga ordanagram från resultatet.

När jag äntligen spårade en vanlig textsträng på ~ 130.000 engelska ord för att använda som min ordlista behövde jag sedan konvertera den här listan till JS.Så jag byggde en funktion för att skära strängen i varje utrymme och skriva ut strukturen för ett objekt med nyckelegenskaper, så att jag mycket snabbt kunde testa giltigheten för vilket ord som helst via worldList["word"] -> returns true if word is valid.

Att skriva ut en lista med 130 000 ord i dokumentet som en JSON-sträng är, precis som din funktion, väldigt dyr.

---

… Och relevansen:

Så här är ditt problem som möter det jag själv uppfann. Hur bearbetar du en mycket dyr slinga utan att krascha en webbsida?

När jag experimenterade med möjligheterna Jag upptäckte faktiskt ett sätt att låta min funktion hantera 130 000 ord och din funktion för att upprätthålla ett ord av vilken storlek som helst genom att balansera arbetsbelastningen över tid.

loopar är ibland för snabba för sitt eget bästa

Slingorna är gjorda så snabba som möjligt, vilket är perfekt för de flesta av de uppgifter vi använder dem för på webbsidor. Men om vi ber dem att hantera för mycket kan webbläsaren inte hantera det.

Så jag behövde en lösning som skulle göra det möjligt för mig att distribuera arbetsbelastningen över tiden för att låta sidan hantera dyra slingor utan problem.

Min lösning var att bygga en manuell slinga via en funktion som kallade sig x gånger och infogade en 1-2ms fördröjning mellan iterationer. Detta gav sidan tillräckligt med tid för att hantera slingan , som utan fördröjningen bearbetade ord vansinnigt snabbt tills C: erna innan de kraschar varje gång. Detta fungerade bra för att skapa min JSON-ordlistastruktur.

Men en fördröjd slinga var extremt svår att implementera i din redan rekursiva funktion.

Jag insåg då att detta är den perfekta situationen för att använda en lösning som jag nyligen läst om för JavaScript …

---

JavaScript Iteratorer och generatorer

Så här kommer JavaScript Iteratorer & Generatorer till undsättning.

Nu är den här recensionen redan en risk för att bli ett monster, så istället för att förklara generatorer kommer jag att citera detta snart blir populärt svar ”s one-liner:

TL; DR: essensen av [med hjälp av en] generator är att kontrollera avstängningen av kodkörningen.

Och förklara enkelt att generatorer på ett bättre sätt implimenterar iteratorer.

Du kan läsa resten själv i svaret där. Om svaret inte gör det åt dig kan du förbättra din förståelse via följande resurser:

• Javascript ”s Framtid: Generatorer

• Generatorer: ett bättre sätt att bygga Iteratorer

• Generatorer – MDN

• Vad kallas det här för generatorer?

Nu har generatorer stor potential i uppgiften att undvika återuppringning helvete, men vi kommer att använda dem här inte för att formatera & struktur, utan för prestanda, vilket är (enligt min prestationsförutspådda åsikt) den mest eleganta anledningen att använda dem.

Jag är ännu inte säker på om generatorerna är den bästa lösningen här, men de är den bästa idén som jag har, och detta är en ursäkt för att prova dem.

---

Din kod med generatorer

Arbetar med den här lösningen fortfarande. Det borde fungera bra, jag har bara inte tid att avsluta ännu och ville erbjuda den förbättrade koden snarare än senare. Jag kommer att lägga upp den här lösningen snart.

Uppdatering: Några dagar senare har jag inte slutat lära mig generatorer, så att jag kan skriva denna funktion korrekt med dem. Jag kommer definitivt att lägga upp den här så snart jag förstår deras syntax bara lite bättre.

---

Och slutligen, eftersom generatorer är nya och inte stöds överallt än .. En förbättrad version av din kod utan dem

Obs! Min formateringsmetod är i allmänhet min egen läsbarhet preferens snarare än bästa praxis. Känn dig inte skyldig att formatera din kod på detta sätt.

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

Genom att deklarera variabler utanför slingorna sparar vi betydligt, som du kommer att se i resultaten. Jag tror också att word.slice() presterade lite bättre än word.substr(). mellan de två av dessa optimeringar, den här koden utför vara mer än din ursprungliga kod.

---

Och sist men inte minst, resultatet blir resultatet!

Originalkod : Resultat uppdaterade! Sidan kraschar inte utan loggning.

• ”code”, 4 tecken: 24 resultat , ~ 1ms
• ”kodare”, 5 tecken: 120 resultat , ~ 1ms
• ”codere”, 6 tecken: 720 resultat , ~ 6ms
• ”coderev”, 7 tecken: 5040 resultat , ~ 11ms
• ”coderevi”, 8 tecken: 40 320 resultat , ~ 75ms
• ”coderevie”, 9 tecken: 362880 resultat , sidan misslyckades
• ”codereview”, 10 tecken: 3628800 resultat , sidfel

Förbättrad kod : Resultat uppdaterade – sidan kraschar inte utan loggning.

• ” code ”, 4 tecken: 24 resultat , ~ 0,5ms
• ” kodare ”, 5 tecken: 120 resultat , ~ 0,5ms
• ”codere”, 6 tecken: 720 resultat , ~ 1,5ms
• ”coderev”, 7 tecken: 5040 resultat , ~ 8ms
• ” coderevi ”, 8 tecken: 40 320 resultat , ~ 53ms
• ” coderevie ”, 9 tecken: 362 880 resultat , ~ 556ms
• ”codereview”, 10 tecken: 3,628,800 resultat , ~ 12725ms

Realtid med generatorer

(Koden är inte komplett – Generatorer visar sig vara svåra)

Jag använde console.time() för att uppnå mätningar exakta till närmaste millisekund, genomföra 3-5 försök vardera och uppskatta ett allmänt genomsnitt baserat på r resultat. Dessa resultat kommer naturligtvis att variera från maskin till maskin. Tiden jämförelser är nyckeln till att läsa riktmärken, inte hastigheterna.

---

Tl; Dr Sammanfattning, som lovat

Loops är en extremt kraftfull verktyg i programmering, men de hanterar inte monsterantal dyra iterationer bra i webbläsaren. Dyra slingfunktioner som denna fungerar dock perfekt om du fördelar arbetsbelastningen över tiden. Ett intressant sätt att göra detta är att använda JS Generators , en ny leksak som finns tillgänglig i webbutiker idag, men inte nödvändigtvis på de lokala marknaderna, så använd försiktigt tills JS 2.0 implementeras mer! Genom att använda kraften från JS-generatorer, vi kan hantera långvariga dyra processer utan att se några prestandaproblem.

Kommentarer

• Gjorde har du någonsin räknat ut generatorer?
• @megawac Jag tillbringade många timmar på det, utan tillräckligt med guider / info / självstudier för att verkligen ta reda på hur man gör det. Jag ’ jag har spenderat så mycket tid som jag har ledigt varje dag sedan det här inlägget för att studera dem, men … jag lär mig inte ’ snabbt från rådokumentationen. Känner du till några bra resurser på generatorer och iteratorer?
• Låter som en bra stackoverflow-tråd @ jt0dd
• Jag skrev en lösare för den lokala tidningen ’ Jumble-pussel. Jag hade en lista med 600 000 ord som jag förbehandlade för att sortera bokstäverna i varje ord. Jag gjorde sedan samma sak för sökbokstäverna och försökte hitta ord. Det kan söka efter alla ord mellan 4 och 10 bokstäver med 10 bokstäver i millisekunder. Bokstäverna ’ throb ’ inmatade i valfri ordning resulterar i ’ bhort ’ som länkar direkt till ’ throb ’ och ’ buljong ’, du behöver inte prova alla kombinationer. Om du till exempel letar efter fyra bokstäver som ges 5 bokstäver finns det bara fyra kombinationer när bokstäverna är sorterade, 120 om inte.
• @ jt0dd I ’ m förvirrad om användningen av word.length + 1 när du använder skiva. Kan du snälla förklara?

Jag tittade på @ jt0dds kod och undrade hur vi kan hantera några fler fall. Jag berättar, låter vi lägga till ett cachelager och förberäkna längderna på de resulterande matriserna!

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 som ” s ful! Jag hoppas att hela den tiden inte var för ingenting …

Förberäknade hash-filer

• ”kod”, 4 tecken: 24 resultat , < = 1ms
• ”kodare”, 5 tecken: 120 resultat , < = 1ms
• ”codere”, 6 tecken: 720 resultat , < = 1ms
• ”coderev”, 7 tecken: 5040 resultat , < = 3ms
• ” coderevi ”, 8 tecken: 40 320 resultat , < = 18ms
• ”coderevie”, 9 tecken: 362 880 resultat , 135ms
• ”codereview”, 10 tecken: 3 628 800 resultat , 2,1 s

Whoopy, vi mötte utmaningen. Låt oss se hur mycket längre vi kan gå. codereview är ett svårt ord som bara duplicerar e tecken. Låt oss prova något lättare för nästa låt oss försöka "anagramarmy"

… … …

Okej, jag slog av mer än vad min webbläsare kan tugga det verkar som om 40 miljoner strängpermutationer verkar vara utanför gränsen 🙁

Du kommer att märka att jag omformade algoritmen för att undvika stacköverflöde – uppslag borde göras utanför rekursionen.

Vi kan öka risken för att vår algoritm inte kraschar genom att göra den asynkron och göra varje ord 100,000 element varje millisekund för att undvika stopp.

Kommentarer

• Fantastiskt! Det här är mycket bättre än generatorversionen jag ’ jag arbetar på. +1 ( Detta svar bör accepteras, det ’ kommer att bli överlägset effektivare än min generatorlösning.)
• Strålande … Bara lysande. Jag verkligen så här. När jag är klar med lösningen i realtid för harmoni-generator (eller så kan du implementera din egen) är du välkommen att ta det och göra detsamma med det. Det ’ kommer att vara långsammare, men ger resultat i realtid och har inget slut på hur stort ett ord det klarar.
• ahh, mjolka slog oss både av far .
• Hej, hur kör jag den här koden längs html och css i min domän? Jag ’ använder den här fria: morsetovoynich.000webhostapp.com

Jag gjorde två skript:

1. Det första är snabbt men kan inte hålla mycket;
2. Den andra är långsam men kan visa obegränsade resultat.

Båda använder prototyp som jag skapade: fastPush, fastSplit och fastJoin; som är snabbare än standardmetoden split och join. använd bitvis för att kontrollera om det är udda eller jämnt, för jag vet att mod är den långsammaste operationen som är möjlig på en dator.

Det första skriptet slår det snabbaste resultatet av andra med över 750 ms (i genomsnitt) på 10chars utmaning av 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()); 

Hur som helst har det här första programmet en gräns och bryter sidan om du försöker mer än 10 tecken.

Det andra programmet (det en nedan) använder en självpåkallande funktion och loggar in på konsolbitarna av 4e4-element, det rensar anagramarrayen varje gång den matar ut en bit och rensar också co nsole.log varje 5 bitar (tillräckligt för att du ska se dessa kombinationer). För att själv anropa funktionen använder programmet setZeroTimeout ( David Barons blogg ) istället för setTimeout eftersom setTimeout är långsammare.

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

Ännu en variant (skriven i C) med en enkel räknare över Power Set för alla strängar.

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

Kör med utskrift av alla strängar:

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

Kommentarer

• Vad menar du med ” utskrift av alla strängar ”? Din funktion matar bara ut delar av ordet, t.ex. om run`-anagram abc`-utgångar a,b,ab,c,ac,bc,abc

Typade matriser för bättre prestanda.

Med den accepterade svarmetoden kan du tredubbla prestandan.

Att köra det vinnande svaret på min maskin gav benchmarked

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

Och när du använder t yped arrays

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

för 3,68 prestandahöjning.

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

För att kanta lite mer du kan fördefiniera resultatmatrisen för att få

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

För att förbättra den upp till 3,95 gånger så snabbt som det vinnande svaret.