Generer alle mulige bokstavkombinasjoner i et 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("") 

Jeg skal kaste hatten min i ringen med den iterative versjonen av Heaps metode for å generere permutasjoner. Det tok litt tid å komme rett, da referansekilde har en skrivefeil 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 noen eksempler på tider for å telle anagrammene til «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

• Dette er av langt vinneren, beregner 3,628,800 resultater i ~5,000ms !
• Hyggelig! Du bør forhåndsberegne matrisestørrelsene vil sannsynligvis gi enda større resultater (ettersom anagrammer og teller er massive matriser). Jeg tror jeg kommer til å prøve å måtte ta en distribuert tilnærming for å slå denne 🙂
• Det ‘ er interessant hvordan dette skalerer med forskjellige størrelsesinnganger jsperf.com/getanagramsc-r/2
• @megawac Jeg vil være interessert i å se din tilnærming etter å ha brukt styrkene til denne tilnærmingen.

Da jeg jobbet med en bedre løsning, fant jeg ut en god bruk for den nye JS Iterators & Generatorer , som jeg har lest om. Jeg brukte sannsynligvis 6 timer i dag på å fikle med denne løsningen, og det var verdt hvert minutt. Du har noen formateringsfeil, men Jeg kommer til å fokusere fullstendig på ytelse og forlate formateringen til de andre korrekturleserne.

---

Å kjøre dette mot et stort ord vil steke maskinen din

Ok, så kanskje det går lite også langt, men seriøst, dette er en kostbar funksjon. Jeg er ingen matematisk guru, så Jeg stilte dette spørsmålet på Math.SE .

Formelen for beregning av antall mulige kombinasjoner er ekstremt bratt:

Tenk på det slik:

Hvor mange valg har du for første bokstav? Fire: 4_ _ _ _.

For det andre? Tre: 4⋅3 _ _.

Fortsett slik, og du finner ut at det er 4⋅3⋅2⋅1 = 4! = 24 valg totalt. – MrRicci

Kjører funksjonen din mot ordet «Encyclopedia» vil resultere i en klar sidekrasj hvis du kjører den på klientsiden. Så for å fikse det, tenkte jeg litt.

---

Ta med meg – dette blir mer og mer relevant når du leser.

Jeg ville prøve å generere ekte ord (ha det gøy med codez)

En anagram er en type ordspill, resultatet av å omorganisere bokstavene i et ord eller en setning for å produsere et nytt ord eller en ny setning, ved å bruke alle de originale bokstavene nøyaktig en gang – Wikipeda

Når jeg tenker på et anagram, tenker jeg på at resultatet blir ekte ord eller uttrykk. Nå, mens formålet med denne kodevurderingen ikke er å endre funksjonaliteten til koden din, kunne jeg ikke annet enn å ha det gøy med den. Så jeg bestemte meg for å søke etter en løsning som tillater meg å filtrere ut og skrive ut ekte ordanagrammer fra resultatet.

Når jeg endelig har sporet en ren tekststreng på ~ 130.000 engelske ord for å bruke som ordliste, trengte jeg da å konvertere denne listen til JS.Så jeg bygde en funksjon for å skjære strengen i hvert rom, og skrive ut strukturen for et objekt med tastede egenskaper, slik at jeg veldig raskt kunne teste gyldigheten til hvilket som helst ord via worldList["word"] -> returns true if word is valid.

Å skrive ut en liste med 130 000 ord i dokumentet som en JSON-streng er, som din funksjon, veldig dyrt.

---

… Og relevansen:

Så her er problemet ditt som møter det jeg oppfant for meg selv. Hvordan behandler du en veldig dyr sløyfe uten å krasje en webside?

Ved å eksperimentere med mulighetene, oppdaget jeg faktisk en måte å la funksjonen min håndter 130 000 ord, og funksjonen din for å opprettholde et ord av alle størrelser , ved å balansere arbeidsmengden over tid.

Sløyfene er noen ganger for raske for sitt eget beste

Loops er laget for å være så raske som mulig, noe som er perfekt for de fleste av oppgavene vi bruker dem til på websider. Men hvis vi ber dem om å håndtere for mye, kan nettleseren ikke takle det.

Så jeg trengte en løsning som tillater meg å distribuere arbeidsbelastningen over tid, for å la siden håndtere dyre sløyfer uten problem.

Min løsning var å bygge en manuell sløyfe via en funksjon som kalte seg x ganger, og satte inn 1-2ms forsinkelse mellom iterasjoner. Dette ga siden nok tid til å håndtere sløyfen , som uten forsinkelsen behandlet ord sinnsykt fort til C-ene før de krasjer hver gang. Dette fungerte bra for å generere JSON-ordlistestrukturen.

Men en forsinket sløyfe var ekstremt vanskelig å implementere i din allerede rekursive funksjon.

Jeg skjønte da at dette er den perfekte situasjonen for å bruke en løsning som jeg nylig har lest om for JavaScript …

---

JavaScript Iteratorer og generatorer

Så, her kommer JavaScript Iteratorer & Generatorer til unnsetning.

Nå er denne anmeldelsen allerede en risiko for å bli et monster, så i stedet for å forklare generatorer, vil jeg sitere dette snart blir et populært svar «s one-liner:

TL; DR: essensen av [ved hjelp av en] generator er å kontrollere suspensjonen av kodeutførelsen.

Og forklar ganske enkelt at generatorer er på en bedre måte å implimentere iteratorer.

Du kan lese resten selv i svaret der. Hvis svaret ikke gjør det for deg, kan du forbedre forståelsen din via følgende ressurser:

• Javascript «s Fremtid: Generatorer

• Generatorer: en bedre måte å bygge Iteratorer

• Generatorer – MDN

• Hva kalles dette for generatorer?

Nå har generatorer stort potensiale i oppgaven med å unngå tilbakeringing i helvete, men vi skal være å bruke dem her ikke for formatering av & struktur, men for ytelse, som er (etter min ytelsesdrivende mening) den mest elegante grunnen til å bruke dem.

Jeg er ikke sikker ennå på om generatorene er den beste løsningen her, men de er den beste ideen jeg har, og dette er en unnskyldning for å prøve dem.

---

Koden din med generatorer

Arbeider med denne løsningen fremdeles. Det skal fungere fint, jeg har bare ikke tid til å fullføre ennå, og ønsket å tilby den forbedrede koden før heller enn senere. Jeg legger ut denne løsningen snart.

Oppdatering: Noen dager senere har jeg ikke ferdig med å lære generatorer, til det punktet å kunne skrive denne funksjonen riktig med dem. Jeg vil definitivt legge den ut her så snart jeg finner syntaksen deres litt bedre.

---

Og til slutt, siden generatorer er nye og ikke støttes overalt ennå. En forbedret versjon av koden din uten dem

Merk: Formateringspraksisen min er generelt min egen lesbarhet preferanse fremfor beste praksis. Ikke føl deg forpliktet til å formatere koden din på denne måten.

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

Ved å erklære variabler utenfor løkkene, sparer vi betydelig, som vil du se i resultatene. Jeg tror også at word.slice() har prestert litt bedre enn word.substr(). mellom de to av disse optimaliseringene, denne koden utfører være mer enn den opprinnelige koden.

---

Og sist men ikke minst, resultatene!

Opprinnelig kode : Resultatene er oppdatert! Siden krasjer ikke uten å logge.

• «code», 4 tegn: 24 resultater , ~ 1ms
• «koder», 5 tegn: 120 resultater , ~ 1ms
• «codere», 6 tegn: 720 resultater , ~ 6ms
• «coderev», 7 tegn: 5040 resultater , ~ 11ms
• «coderevi», 8 tegn: 40320 resultater , ~ 75ms
• «coderevie», 9 tegn: 362880 resultater , side mislyktes
• «codereview», 10 tegn: 3,628,800 resultater , sidefeil

Forbedret kode : Resultater oppdatert – siden krasjer ikke uten å logge.

• » code «, 4 tegn: 24 resultater , ~ 0,5ms
• » koder «, 5 tegn: 120 resultater , ~ 0,5ms
• «codere», 6 tegn: 720 resultater , ~ 1,5ms
• «coderev», 7 tegn: 5040 resultater , ~ 8ms
• » coderevi «, 8 tegn: 40 320 resultater , ~ 53ms
• » coderevie «, 9 tegn: 362,880 resultater , ~ 556ms
• «codereview», 10 tegn: 3,628,800 resultater , ~ 12725ms

Sanntid med generatorer

(Koden er ikke fullført – Generatorer viser seg litt vanskelig)

Jeg brukte console.time() for å oppnå målinger nøyaktig til nærmeste millisekund, fullføre 3-5 forsøk hver, og estimere et generelt gjennomsnitt basert på r esults. Disse resultatene vil selvfølgelig variere fra maskin til maskin. Tiden sammenligninger er nøkkelen til å lese referanser, ikke hastighetene.

---

Tl; Dr Sammendrag, som lovet

Loops er en ekstremt kraftig verktøy i programmering, men de håndterer ikke monstertall med dyre iterasjoner godt i nettleseren. Dyre loopingsfunksjoner som dette fungerer imidlertid perfekt hvis du fordeler arbeidsmengden over tid. En interessant måte å gjøre dette på er å bruke JS Generators , et nytt leketøy tilgjengelig i nettbutikker i dag, men ikke nødvendigvis i de lokale markedene, så bruk forsiktig til JS 2.0 er mer implementert! Ved å utnytte kraften til JS-generatorer, vi kan administrere langvarige dyre prosesser uten å se noen ytelsesproblemer.

Kommentarer

• Gjorde har du noen gang funnet ut generatorer?
• @megawac Jeg brukte mange timer på den, uten nok guider / info / tutorials til å virkelig finne ut hvordan jeg gjør det. Jeg ‘ jeg har brukt så mye tid som jeg har ledig hver dag siden dette innlegget til å studere dem, men … Jeg lærer ikke ‘ t å lære raskt av rådokumentasjonen. Kjenner du til noen gode ressurser på generatorer og iteratorer?
• Høres ut som en god stackoverflow-tråd @ jt0dd
• Jeg skrev en løser for lokalavisen ‘ s Jumble puzzle. Jeg hadde en liste med 600 000 ord som jeg forhåndsbehandlet for å sortere bokstavene i hvert ord. Jeg gjorde det samme for søkebokstavene og prøvde å finne ord. Det kan skanne etter alle ord mellom 4 og 10 bokstaver gitt 10 bokstaver i millisekunder. Bokstavene ‘ throb ‘ angitt i hvilken som helst rekkefølge resulterer i ‘ bhort ‘ som lenker direkte til ‘ throb ‘ og ‘ buljong ‘, ikke nødvendig å prøve hver kombinasjon. For eksempel hvis du leter etter ord på 4 bokstaver gitt 5 bokstaver, er det bare fire kombinasjoner når bokstavene er sortert, 120 hvis ikke.
• @ jt0dd I ‘ er forvirret om bruken av word.length + 1 når du bruker skive. Kan du forklare det?

Jeg tok en titt på @ jt0dds kode og lurte på hvordan vi kunne håndtert noen flere tilfeller. Jeg forteller deg, la oss legge til et cachelag og beregne lengdene på de resulterende matriser!

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 stygt! Jeg håper hele tiden ikke var forgjeves …

Forhåndsberegnede hash

• «kode», 4 tegn: 24 resultater , < = 1ms
• «koder», 5 tegn: 120 resultater , < = 1ms
• «codere», 6 tegn: 720 resultater , < = 1ms
• «coderev», 7 tegn: 5040 resultater , < = 3ms
• » coderevi «, 8 tegn: 40 320 resultater , < = 18ms
• «coderevie», 9 tegn: 362 880 resultater , 135ms
• «codereview», 10 tegn: 3.628.800 resultater , 2,1 s

Whoopy, vi møtte utfordringen. La oss se hvor mye lenger vi kan gå. codereview er et vanskelig ord som bare dupliserer e tegn. La oss prøve noe enklere for det neste la oss prøve "anagramarmy"

… … …

Ok, jeg har litt mer enn nettleseren min kan tygge. det ser ut til at 40 millioner strengpermutasjoner ser ut til å være utenfor grensen 🙁

Du vil legge merke til at jeg redesignet algoritmen for å unngå stabeloverløp – oppslag burde gjøres utenfor rekursjonen.

Vi kan øke sjansen for at algoritmen vår ikke krasjer ved å gjøre den asynkron og gjøre hvert ord 100,000 elementer hvert millisekund for å unngå å stoppe.

Kommentarer

• Kjempebra! Dette er mye bedre enn generatorversjonen jeg ‘ jeg jobber med. +1 ( Dette svaret bør godtas, det ‘ kommer til å være langt mer effektivt enn generatorløsningen min.)
• Strålende … Bare strålende. Jeg virkelig som dette. Når jeg er ferdig med sanntidsløsningen for harmonigenerator (eller du kan implementere din egen), er du velkommen til å ta det og gjøre det samme med det. Det ‘ vil være tregere, men gir resultater i sanntid og har ingen slutt på hvor stort et ord det kan takle.
• ahh, mjolka slo oss begge av far .
• Hei, hvordan utfører jeg denne koden langs html og css på domenet mitt? Jeg ‘ bruker denne gratisen: morsetovoynich.000webhostapp.com

Jeg laget to skript:

1. Den første er rask, men kan ikke holde mye;
2. Det andre er tregt, men kan vise ubegrensede resultater.

Begge bruker prototypen jeg laget: fastPush, fastSplit og fastJoin; som er raskere enn standardmetoden splittes og blir sammen. bruk bitvis for å sjekke om det er rart eller jevnt, for jeg vet at mod er den tregeste operasjonen som er mulig på en datamaskin.

Det første skriptet slår det raskeste resultatet av andre med over 750ms (på gjennomsnitt) på 10chars utfordring med permutasjon .

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

Uansett har dette første programmet en grense og bryter siden hvis du prøver mer enn 10 tegn.

Det andre programmet (det en nedenfor) bruker en selvinnkallende funksjon og logger seg på konsollbiter av 4e4-elementer, det tømmer anagrammatrisen hver gang den sender ut en del og tømmer også co nsole.log hver 5 biter (nok til at du kan se disse kombinasjonene). For selv å påkalle funksjonen bruker programmet setZeroTimeout ( David Barons blogg ) i stedet for setTimeout fordi setTimeout er langt tregere.

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

Nok en annen variant (skrevet i C) ved hjelp av en enkel teller over Power Set av alle strenger.

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

Kjør med utskrift av alle strenger:

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

Kommentarer

• Hva mener du med » utskrift av alle strenger «? Din funksjon sender bare ut deler av ordet, f.eks. hvis run`-anagrammer abc`-utganger a,b,ab,c,ac,bc,abc

Skrivte matriser for bedre ytelse.

Ved å bruke den aksepterte svarmetoden kan du tredoble ytelsen.

Å kjøre det vinnende svaret på maskinen min ga benchmarked

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

Og når du bruker t yped arrays

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

for 3,68 ytelsesøkning.

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

For å kanten litt mer du kan forhåndsdefinere resultatmatrisen for å få

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

For å forbedre den opptil 3,95 ganger så raskt som det vinnende svaret.