Genereer alle mogelijke combinaties van letters in een woord

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

Ik ga mijn hoed in de ring gooien met de iteratieve versie van Heap “s methode voor het genereren van permutaties. Het kostte me een tijdje om het goed te krijgen, omdat mijn referentiebron een typefout heeft in het algoritme -_-.

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

Met enkele voorbeeldtimings om de anagrammen van “codereview” te tellen:

$ 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 

Reacties

• Dit is met verreweg de winnaar, die 3.628.800 resultaten in ~5.000ms!
• Leuk! Als u de grootte van de array vooraf zou moeten berekenen, zal dit waarschijnlijk nog betere resultaten opleveren (aangezien anagrammen en teller enorme arrays zijn). Ik denk dat ik ga proberen een gedistribueerde aanpak te gebruiken om deze te verslaan 🙂
• Het is ‘ interessant hoe dit kan worden geschaald met ingangen van verschillende grootte jsperf.com/getanagramsc-r/2
• @megawac Ik zou graag je aanpak willen zien nadat ik de sterke punten van deze aanpak heb benut.

Terwijl ik aan een betere oplossing werkte, kwam ik erachter dat het nieuwe JS Iterators & Generatoren , waarover ik heb gelezen. Ik heb vandaag waarschijnlijk 6 uur aan deze oplossing gehannes, en het was elke minuut waard. “Je hebt wat opmaakfouten, maar Ik ga me volledig concentreren op prestaties en verlaat de opmaak aan de andere recensenten.

---

Als je dit tegen een groot woord gebruikt, zal je machine frituren

Ok, dus misschien gaat dat ook een klein ver, maar serieus, dit is een dure functie. Ik “ben geen wiskundegoeroe, dus Ik heb deze vraag gesteld op Math.SE .

De formule voor het berekenen van het aantal mogelijke combinaties is extreem steil:

Zie het als volgt:

Hoeveel keuzes heeft u voor de eerste letter? Vier: 4_ _ _ _.

Voor de tweede? Drie: 4⋅3 _ _.

Ga zo door en je zult zien dat er in totaal 4⋅3⋅2⋅1 = 4! = 24 keuzes zijn. – MrRicci

Uw functie uitvoeren tegen het woord “Encyclopedia” zal resulteren in een definitieve crash van de pagina als u het client-side draait. Dus om dat op te lossen, heb ik wat nagedacht.

---

Houd rekening met me – Dit wordt steeds relevanter naarmate je leest.

Ik wilde proberen echte woorden te genereren (plezier hebben met de codez)

Een anagram is een soort woordspel, het resultaat van het herschikken van de letters van een woord of zin om een nieuw woord of zin te produceren, waarbij alle originele letters precies één keer worden gebruikt – Wikipeda

Als ik aan een anagram denk, denk ik dat het resultaat echte woorden of zinsdelen zijn. Hoewel het doel van deze codereview niet is om de functionaliteit van je code te veranderen, kon ik het niet helpen, maar ik wil er wat plezier mee hebben. Dus besloot ik te zoeken naar een oplossing waarmee ik alle echte woordanagrammen uit het resultaat kon filteren en afdrukken.

Toen ik eindelijk een reeks platte tekst van ~ 130.000 Engelse woorden om als mijn woordenlijst te gebruiken, ik moest deze lijst vervolgens omzetten in JS.Dus bouwde ik een functie om de string op elke spatie te splitsen en de structuur af te drukken voor een object met sleuteleigenschappen, zodat ik heel snel de geldigheid van elk woord kon testen via worldList["word"] -> returns true if word is valid.

Het afdrukken van een lijst van 130.000 woorden in de hoofdtekst van het document als een JSON-string is, net als uw functie, erg duur.

---

… en de relevantie:

Dus hier komt uw probleem samen met het probleem dat ik voor mezelf heb bedacht. Hoe verwerk je een erg dure lus zonder een webpagina te laten crashen?

Door te experimenteren met de mogelijkheden, ontdekte ik eigenlijk een manier om mijn functie toe te staan verwerken 130.000 woorden, en uw functie om een woord van elke grootte te ondersteunen , door de werkbelasting in de tijd te verdelen.

Loops zijn soms te snel voor hun eigen bestwil

Lussen zijn gemaakt om zo snel mogelijk te zijn, wat perfect is voor de meeste van de taken waarvoor we ze gebruiken op webpaginas. Maar als we hen vragen te veel te verwerken, kan de browser het “niet aan.

Dus ik had een oplossing nodig waarmee ik de werklast over de tijd kon verdelen, zodat de pagina het aankan dure loops zonder problemen.

Mijn oplossing was om een handmatige loop te bouwen via een functie die zichzelf x keer noemde, en een 1-2ms vertraging tussen iteraties. Dit gaf de pagina genoeg tijd om de lus af te handelen, die zonder de vertraging woorden verwerkte waanzinnig snel tot de Cs voordat ze elke keer crashten. Dit werkte prima voor het genereren van mijn JSON-woordenlijststructuur.

Maar een vertraagde lus was buitengewoon lastig te implementeren in je reeds recursieve functie.

Ik realiseerde me toen dat dit de perfecte situatie is om een oplossing te gebruiken waarover ik onlangs heb gelezen voor JavaScript …

---

JavaScript-iteratoren en -generatoren

Dus hier komen JavaScript-iteratoren & -generatoren te hulp.

Nu, deze recensie is al een risico om een monster te worden, dus in plaats van Generators uit te leggen, “ga ik citeren en dit wordt binnenkort een populair antwoord “s one-liner:

TL; DR: de essentie van [het gebruiken van een] generator is het controleren van de opschorting van de code-uitvoering.

En leg eenvoudig uit dat generatoren een verbeterde manier hebben om iteratoren te implementeren.

Je kunt de rest zelf lezen in het antwoord daar. Als dat antwoord “niet helemaal bij je past, kun je je begrip verbeteren via de volgende bronnen:

• Javascript” s Future: Generators

• Generatoren: een betere manier om iteratoren te bouwen

• Generatoren – MDN

• Hoe wordt dit generatoren genoemd?

Nu hebben generatoren een groot potentieel in het vermijden van callback-hel, maar we gaan gebruik ze hier niet voor het formatteren van de & -structuur, maar voor prestaties, wat (naar mijn prestatiegerichte mening) de meest elegante reden is om ze te gebruiken.

Ik “weet nog niet zeker of de generatoren hier de beste oplossing zijn, maar ze zijn het beste idee dat ik heb, en dit is een excuus om ze uit te proberen.

---

Uw code met generatoren

Werken aan deze oplossing nog steeds. Het zou prima moeten werken, ik heb gewoon nog geen tijd om het af te maken en ik wilde de verbeterde code eerder dan later aanbieden. Ik zal deze oplossing binnenkort posten.

Update: een paar dagen later ben ik nog niet klaar met het leren van generatoren, tot het punt dat ik deze functie er correct mee kan schrijven. Ik zal het hier zeker posten zodra ik weet dat hun syntaxis net iets beter is.

---

En tot slot, aangezien generatoren nieuw zijn en nog niet overal worden ondersteund .. Een verbeterde versie van uw code zonder hen

Opmerking: mijn opmaakmethoden zijn over het algemeen mijn eigen leesbaarheid voorkeur in plaats van best practice. Voel je niet verplicht om je code op deze manier op te maken.

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

Door variabelen buiten de loops te declareren, besparen we aanzienlijk, aangezien je zult zien in de resultaten. Ook denk ik dat word.slice() iets beter presteerde dan word.substr(). tussen de twee van die optimalisaties, deze code presteert zijn tter dan uw originele code.

---

En Last but not Least, de prestatieresultaten!

Originele code : resultaten bijgewerkt! De pagina crasht niet zonder te loggen.

• “code”, 4 tekens: 24 resultaten , ~ 1ms
• “coder”, 5 tekens: 120 resultaten , ~ 1ms
• “codere”, 6 tekens: 720 resultaten , ~ 6ms
• “coderev”, 7 tekens: 5040 resultaten , ~ 11ms
• “coderevi”, 8 tekens: 40.320 resultaten , ~ 75ms
• “coderevie”, 9 tekens: 362.880 resultaten , pagina mislukt
• “codereview”, 10 tekens: 3.628.800 resultaten , pagina mislukt

Verbeterde code : Resultaten bijgewerkt – Pagina crasht niet zonder loggen.

• ” code “, 4 tekens: 24 resultaten , ~ 0,5 ms
• ” coder “, 5 tekens: 120 resultaten , ~ 0,5 ms
• “codere”, 6 tekens: 720 resultaten , ~ 1.5ms
• “coderev”, 7 tekens: 5040 resultaten , ~ 8ms
• ” coderevi “, 8 karakters: 40.320 resultaten , ~ 53ms
• ” coderevie “, 9 karakters: 362.880 resultaten , ~ 556ms
• “codereview”, 10 tekens: 3.628.800 resultaten , ~ 12725ms

Real-time met generatoren

(Code niet compleet – Generatoren blijken een beetje moeilijk)

Ik gebruikte console.time() om metingen te verkrijgen die tot op de dichtstbijzijnde milliseconde nauwkeurig zijn, elk 3-5 tests uitvoeren en een algemeen gemiddelde schatten op basis van de r resultaten. Deze resultaten zullen natuurlijk van machine tot machine verschillen. De tijd vergelijkingen zijn de sleutel tot het lezen van benchmarks, niet de snelheden.

---

Tl; Dr Samenvatting, zoals beloofd

Loops zijn een buitengewoon krachtige tool bij het programmeren, maar ze kunnen grote aantallen dure iteraties niet goed aan in de webbrowser. Dure looping-functies zoals deze presteren perfect, maar als je de werklast over de tijd verdeelt. Een interessante manier om dit te doen is door JS Generators te gebruiken , een nieuw speeltje dat tegenwoordig in webwinkels verkrijgbaar is, maar niet noodzakelijkerwijs op de lokale markten, dus gebruik het voorzichtig totdat JS 2.0 breder wordt geïmplementeerd! Door de kracht van JS-generatoren te gebruiken, we kunnen langlopende dure processen beheren zonder prestatieproblemen te zien.

Opmerkingen

• Wist heb je ooit generatoren ontdekt?
• @megawac Ik heb er vele uren aan besteed, zonder genoeg gidsen / info / tutorials om er echt achter te komen hoe het moet. I ‘ heb uitgegeven zoveel tijd als ik elke dag vrij heb sinds dit bericht om ze te bestuderen, maar … ik ‘ leer niet snel van de ruwe documentatie. Kent u goede bronnen over generatoren en iteratoren?
• Klinkt als een goede stackoverflow-thread @ jt0dd
• Ik schreef een oplosser voor de lokale krant ‘ s Jumble-puzzel. Ik had een lijst met 600.000 scrabble-woorden die ik voorverwerkte om de letters in elk woord te sorteren. Ik deed toen hetzelfde voor de zoekletters en probeerde woorden te vinden. Het kan zoeken naar alle woorden tussen 4 en 10 letters, gegeven 10 letters in milliseconden. De letters ‘ kloppen ‘ die in willekeurige volgorde zijn ingevoerd, resulteren in ‘ bhort ‘ die rechtstreeks verwijst naar ‘ throb ‘ en ‘ bouillon ‘, je hoeft niet elke combinatie te proberen. Als u bijvoorbeeld zoekt naar woorden van 4 letters met 5 letters, zijn er slechts 4 combinaties wanneer de letters zijn gesorteerd, 120 als dat niet het geval is.
• @ jt0dd I ‘ m confused over het gebruik van word.length + 1 bij gebruik van slice. Kun je het alstublieft uitleggen?

Ik heb de code van @ jt0dd bekeken en vroeg me af hoe we kan nog wel wat meer gevallen aan. Ik “zal je vertellen, laten we een cachelaag toevoegen en de lengtes van de resulterende arrays vooraf berekenen!

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 dat” lelijk! Ik hoop dat al die tijd niet voor niets was …

Vooraf berekende hashs

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

Whoopy, we zijn de uitdaging aangegaan. Laten we eens kijken hoeveel verder we kunnen gaan. codereview is een moeilijk woord dat alleen e tekens dupliceert. Laten we iets gemakkelijker proberen voor de volgende gaan. Laten we proberen "anagramarmy"

… … …

Oké, ik beet meer af dan mijn browser aankan het lijkt erop dat 40 miljoen string-permutaties voorbij de limiet lijken te zijn 🙁

Je zult merken dat ik het algoritme opnieuw heb ontworpen om stack-overflow te voorkomen – lookups zouden buiten de recursie moeten worden gedaan.

We kunnen de kans vergroten dat ons algoritme niet crasht door het asynchroon te maken en elk woord 100,000 -elementen elke milliseconde uit te voeren om te voorkomen dat het wordt gestopt.

Opmerkingen

• Geweldig! Dit is veel beter dan de generatorversie waar ik ‘ aan werk. +1 ( Dit antwoord zou geaccepteerd moeten worden, het ‘ zal veel efficiënter zijn dan mijn generatoroplossing.)
• Briljant … Gewoon briljant. Ik echt zoals dit. Als ik klaar ben met de real-time harmoniegeneratoroplossing (of u kunt uw eigen oplossing implementeren), voel u dan vrij om dat te doen en hetzelfde ermee te doen. Het ‘ zal langzamer zijn, maar levert resultaten in realtime op en heeft geen einde aan de grootte van een woord dat het aankan.
• ahh, mjolka heeft ons verslagen beide door far .
• Hallo, hoe voer ik deze code naast html en css uit binnen mijn domein? Ik ‘ gebruik deze gratis: morsetovoynich.000webhostapp.com

Ik heb twee scripts gemaakt:

1. De eerste is snel maar kan “niet veel bevatten;
2. De tweede is traag, maar kan onbeperkte resultaten opleveren.

Beide gebruiken het prototype dat ik heb gemaakt: fastPush, fastSplit en fastJoin, die sneller zijn dan de standaard methode split and join. gebruik bitwise om te controleren of het even of oneven is, omdat ik weet dat mod de langzaamste bewerking is die mogelijk is op een computer.

Het eerste script verslaat het snelste resultaat van anderen met meer dan 750 ms (gemiddeld) op 10chars-uitdaging van permutatie .

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

Hoe dan ook, dit eerste programma heeft een limiet en breekt de pagina als je meer dan 10 tekens probeert.

Het tweede programma (het één hieronder) maakt gebruik van een zelfoproepende functie en logt in op de console-chunks van 4e4-elementen, het wist de anagrammen-array elke keer dat het een chunk uitvoert en wist ook co nsole.log elke 5 brokken (genoeg om je die combinaties te laten zien). Om de functie zelf op te roepen, gebruikt het programma setZeroTimeout ( David Baron “s blog ) in plaats van setTimeout omdat setTimeout veel langzamer is.

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

Nog een andere variant (geschreven i C) met een eenvoudige teller boven de Power Set van alle strings.

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

Uitvoeren met afdruk van alle strings:

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

Reacties

• Wat bedoel je met ” afdruk van alle strings “? Uw functie voert slechts delen van het woord uit, bijv. als run` anagrams abc` outputs a,b,ab,c,ac,bc,abc

Getypte arrays voor betere prestaties.

Met de geaccepteerde antwoordenmethode kun je de prestaties verdrievoudigen.

Het winnende antwoord op mijn machine uitvoeren gaf gebenchmarked

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

En bij gebruik van t yped arrays

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

voor een prestatieverbetering van 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; } 

Om een beetje meer je kunt de resultaatarray vooraf definiëren om

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

te krijgen om het tot 3,95 keer zo snel te verbeteren als het winnende antwoord.