Generer alle mulige kombinationer af bogstaver 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 kaster min hat i ringen med den iterative version af Heaps metode til generering af permutationer. Det tog mig et stykke tid at komme rigtigt, da min referencekilde har en skrivefejl 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 nogle eksempler på tidspunkter for at tælle anagrammerne for “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 langt vinderen, der beregner 3.628.800 resultater inden for ~5.000ms!
• Dejligt! Du burde forudberegne matrixstørrelserne sandsynligvis give endnu større resultater (da anagrammer og tæller er massive arrays). Jeg tror, jeg vil prøve at være nødt til at tage en distribueret tilgang for at slå denne 🙂
• Det ‘ er interessant, hvordan dette skaleres med forskellige størrelsesindgange jsperf.com/getanagramsc-r/2
• @megawac Jeg ville være interesseret i at se din tilgang efter at have udnyttet styrkerne ved denne tilgang.

Da jeg arbejdede på en bedre løsning, fandt jeg ud af en god brug for den nye JS Iteratorer & Generatorer , som jeg har læst om. Jeg brugte sandsynligvis 6 timer i dag på at fikle med denne løsning, og det var hvert minut værd. Du har nogle formateringsfejl, men Jeg vil fokusere fuldstændigt på ydeevne og forlade formateringen til de andre korrekturlæsere.

---

At køre dette mod et stort ord vil stege din maskine

Ok, så måske går det en lille også langt, men seriøst, dette er en dyr funktion. Jeg er ingen matematikguru, så Jeg stillede dette spørgsmål på Math.SE .

Formlen til beregning af antallet af mulige kombinationer er ekstremt stejl:

Tænk på det sådan:

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

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

Fortsæt sådan, og du finder ud af, at der er 4⋅3⋅2⋅1 = 4! = 24 valg i alt. – MrRicci

Kører din funktion mod ordet “Encyclopedia” vil resultere i en bestemt sidekrasj, hvis du kører den på klientsiden. Så for at rette op på det tænkte jeg noget.

---

Bær med mig – Dette bliver mere og mere relevant, når du læser.

Jeg ville prøve at generere rigtige ord (have det sjovt med codez)

En anagram er en type ordspil, resultatet af omarrangering af bogstaverne i et ord eller en sætning for at producere et nyt ord eller en ny sætning ved at bruge alle de originale bogstaver nøjagtigt en gang – Wikipedia

Når jeg tænker på et anagram, tænker jeg på, at resultatet er rigtige ord eller sætninger. Nu, mens formålet med denne kodeanmeldelse ikke er at ændre din kodes funktionalitet, kunne jeg ikke hjælpe, men jeg vil have det sjovt med det. Så jeg besluttede at søge efter en løsning, der gjorde det muligt for mig at filtrere og udskrive ægte ordanagrammer fra resultatet.

Når jeg endelig har sporet en almindelig tekststreng på ~ 130.000 engelske ord for at bruge som min ordliste, havde jeg derefter brug for at konvertere denne liste til JS.Så jeg byggede en funktion til at skære strengen i hvert rum og udskrive strukturen til et objekt med nøgleegenskaber, så jeg meget hurtigt kunne teste gyldigheden af ethvert ord via worldList["word"] -> returns true if word is valid.

Udskrivning af en liste med 130.000 ord i dokumentteksten som en JSON-streng er ligesom din funktion meget dyr.

---

… Og relevansen:

Så her er dit problem, der møder det, som jeg opfandt for mig selv. Hvordan behandler du en meget dyr sløjfe uden at gå ned på en webside?

Når jeg eksperimenterede med mulighederne, opdagede jeg faktisk en måde at lade min funktion håndter 130.000 ord, og din funktion til at opretholde et ord af enhver størrelse ved at balancere arbejdsbyrden over tid.

Loops er undertiden for hurtige til deres eget bedste

Loops er lavet til at være så hurtige som muligt, hvilket er perfekt for de fleste af de opgaver, vi bruger dem til på websider. Men hvis vi beder dem om at håndtere for meget, kan browseren ikke håndtere det.

Så jeg havde brug for en løsning, der gjorde det muligt for mig at distribuere arbejdsbelastningen over tid for at lade siden håndtere dyre sløjfer uden et problem.

Min løsning var at opbygge en manuel sløjfe via en funktion, der kaldte sig x gange og indsatte en 1-2ms forsinkelse mellem gentagelser. Dette gav siden nok tid til at håndtere sløjfen , som uden forsinkelsen behandlede ord sindssygt hurtigt indtil Cerne før de går ned hver gang. Dette fungerede godt til at generere min JSON ordliste struktur.

Men en forsinket sløjfe var ekstremt vanskelig at implementere i din allerede rekursive funktion.

Jeg indså da, at dette er den perfekte situation til at bruge en løsning, som jeg for nylig har læst om til JavaScript …

---

JavaScript Iteratorer og generatorer

Så her kommer JavaScript Iteratorer & Generatorer til undsætning.

Nu er denne anmeldelse allerede en risiko for at blive et monster, så i stedet for at forklare generatorer vil jeg citere dette snart populære svar “s one-liner:

TL; DR: essensen af [ved hjælp af en] generator er at kontrollere suspensionen af kodekørsel.

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

Du kan læse resten for dig selv i svaret der. Hvis svaret ikke gør det for dig, kan du forbedre din forståelse via følgende ressourcer:

• Javascript “s Fremtid: Generatorer

• Generatorer: en bedre måde at opbygge Iteratorer

• Generatorer – MDN

• Hvad kaldes denne ting generatorer?

Nu har generatorer et stort potentiale i opgaven med at undgå tilbagekald helvede, men vi vil bruge dem her ikke til formatering af & struktur, men til ydeevne, som er (efter min opfattelse af præstationer) den mest elegante grund til at bruge dem.

Jeg er endnu ikke sikker på, om generatorerne er den bedste løsning her, men de er den bedste idé, jeg har, og dette er en undskyldning for at prøve dem.

---

Din kode med generatorer

Arbejder med denne løsning stadig. Det skal fungere fint, jeg har bare ikke tid til at afslutte endnu og ville gerne tilbyde den forbedrede kode hurtigere end senere. Jeg vil snart sende denne løsning.

Opdatering: Et par dage senere er jeg ikke færdig med at lære generatorer til det punkt, at jeg kan skrive denne funktion korrekt med dem. Jeg vil helt sikkert sende den her, så snart jeg finder ud af deres syntaks lidt bedre.

---

Og endelig, da generatorer er nye og ikke understøttes overalt endnu .. En forbedret version af din kode uden dem

Bemærk: Min formateringspraksis er generelt min egen læsbarhed præference snarere end bedste praksis. Føler dig ikke forpligtet til at formatere din kode på denne måde.

/* 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 at erklære variabler uden for sløjferne sparer vi betydeligt, som du vil se i resultaterne. Jeg mener også, at word.slice() klarede sig lidt bedre end word.substr(). mellem de to af disse optimeringer, denne kode udfører være tter end din oprindelige kode.

---

Og sidst men ikke mindst, resultaterne resultater!

Oprindelig kode : Resultater opdateret! Siden kolliderer ikke uden at logge.

• “kode”, 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: 40.320 resultater , ~ 75ms
• “coderevie”, 9 tegn: 362.880 resultater , side mislykkes
• “codereview”, 10 tegn: 3.628.800 resultater , sidefejl

Forbedret kode : Opdaterede resultater – siden kolliderer ikke uden logføring.

• ” kode “, 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

Realtid med generatorer

(Koden er ikke komplet – Generatorer viser sig lidt vanskelige)

Jeg brugte console.time() for at opnå målinger nøjagtigt til nærmeste millisekund, gennemføre 3-5 forsøg hver og estimere et generelt gennemsnit baseret på r resultater. Disse resultater vil naturligvis variere fra maskine til maskine. Tiden sammenligninger er nøglen til at læse benchmarks, ikke hastighederne.

---

Tl; Dr. Resume, som lovet

Loops er en ekstremt stærk værktøj til programmering, men de håndterer ikke monsterantal af dyre iterationer godt i webbrowseren. Dyre looping-funktioner som denne fungerer dog perfekt, hvis du fordeler arbejdsbyrden over tid. En interessant måde at gøre dette på er at bruge JS Generators , et nyt legetøj, der er tilgængeligt i webbutikker i dag, men ikke nødvendigvis på de lokale markeder, så brug forsigtigt, indtil JS 2.0 er mere implementeret! Ved at udnytte kraften fra JS-generatorer, Vi kan styre langvarige dyre processer uden at se nogen ydeevneproblemer.

Kommentarer

• Gjorde har du nogensinde fundet ud af generatorer?
• @megawac Jeg brugte mange timer på det uden nok guider / info / tutorials til virkelig at finde ud af, hvordan man gør det. Jeg ‘ jeg har brugt så meget tid som jeg har fri hver dag siden dette indlæg til at studere dem, men … Jeg lærer ikke ‘ ikke hurtigt fra den rå dokumentation. Kender du nogen gode ressourcer til generatorer og iteratorer?
• Lyder som en god stackoverflow-tråd @ jt0dd
• Jeg skrev en løser til det lokale papir ‘ s Jumble puzzle. Jeg havde en liste med 600.000 scrabble-ord, som jeg forbehandlede for at sortere bogstaverne i hvert ord. Derefter gjorde jeg det samme for søgebrevene og forsøgte at finde ord. Det kunne scanne for alle ord mellem 4 og 10 bogstaver, der fik 10 bogstaver i millisekunder. Bogstaverne ‘ throb ‘ indtastet i en hvilken som helst rækkefølge resulterer i ‘ bhort ‘ der linker direkte til ‘ throb ‘ og ‘ bouillon ‘, det er ikke nødvendigt at prøve hver kombination. For eksempel hvis du leder efter ord på 4 bogstaver givet 5 bogstaver, er der kun 4 kombinationer, når bogstaverne er sorteret, 120 hvis ikke.
• @ jt0dd I ‘ m forvirret om brugen af word.length + 1, når du bruger skive. Kan du venligst forklare det?

Jeg kiggede på @ jt0dds kode og spekulerede på, hvordan vi kunne kunne håndtere nogle flere sager. Jeg fortæller dig, lad os tilføje et cachelag og forud beregne længderne af de resulterende arrays! s grimt! Jeg håber, at al den tid ikke var til ingenting …

Forudberegnede hashs

• “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ødte udfordringen. Lad os se, hvor meget længere vi kan gå. codereview er et hårdt ord, der kun duplikerer e tegn. Lad os prøve noget lettere for det næste lad. Lad os prøve "anagramarmy"

… … …

Okay, jeg slog mere, end min browser kan tygge det ser ud til, at 40 millioner strengpermutationer synes at være uden for grænsen 🙁

Du vil bemærke, at jeg redesignede algoritmen for at undgå stackoverløb – opslag burde gøres uden for rekursionen.

Vi kan øge chancen for, at vores algoritme ikke går ned ved at gøre den asynkron og gøre hvert ord 100,000 elementer hvert millisekund for at undgå at stoppe.

Kommentarer

• Awesome! Dette er meget bedre end generatorversionen jeg ‘ jeg arbejder på. +1 ( Dette svar skal accepteres, det ‘ vil være langt mere effektivt end min generatorløsning.)
• Strålende … Bare strålende. Jeg virkelig sådan her. Når jeg er færdig med løsningen i realtid med harmonegenerator (eller måske implementerer du din egen), er du velkommen til at tage det og gøre det samme med det. Det ‘ vil være langsommere, men giver resultater i realtid og har ingen ende på, hvor stort et ord det kan klare.
• ahh, mjolka slog os begge af far .
• Hej, hvordan udfører jeg denne kode langs html og css i mit domæne? Jeg ‘ bruger denne gratis: morsetovoynich.000webhostapp.com

Jeg lavede to scripts:

1. Den første er hurtig, men kan ikke holde meget;
2. Det andet er langsomt, men kan vise ubegrænsede resultater.

Begge bruger prototype, jeg lavede: fastPush, fastSplit og fastJoin; som er hurtigere end standardmetoden split og sammenføjning. brug bitvis til at kontrollere, om det er ulige eller lige, fordi jeg ved, at mod er den langsomste operation, der er mulig på en computer.

Det første script slår det hurtigste resultat af andre med over 750 ms (på gennemsnittet) på 10-chars udfordring af 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()); 

Under alle omstændigheder har dette første program en grænse og bryder siden, hvis du prøver mere end 10 tegn.

Det andet program (det en nedenfor) bruger en selvopkaldende funktion og logger ind på konsolbiterne af 4e4-elementer, det rydder anagrammer arrayet hver gang det udsender et stykke og rydder også co nsole.log hver 5 bidder (nok til at du kan se disse kombinationer). For selv at påkalde funktionen bruger programmet setZeroTimeout ( David Barons blog ) i stedet for setTimeout, fordi setTimeout er langt langsommere.

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

Endnu en anden variant (skrevet i C) ved hjælp af en simpel tæller over Power Set for alle strenge.

#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 udskrivning af alle strenge:

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

Kommentarer

• Hvad mener du med ” print af alle strenge “? Din funktion udsender bare dele af ordet, f.eks. hvis run`-anagrammer abc`-udgange a,b,ab,c,ac,bc,abc

Indtastede arrays for bedre ydeevne.

Ved hjælp af den accepterede svarmetode kan du tredoble performance.

At køre det vindende svar på min maskine gav benchmarked

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

Og når du bruger t ypede arrays

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

for at øge ydeevnen på 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; } 

For at kant lidt mere du kan foruddefinere resultat arrayet for at få

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

For at forbedre det op til 3,95 gange så hurtigt som det vindende svar.