Generați toate combinațiile posibile de litere dintr-un cuvânt

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

Voi arunca pălăria în ring cu versiunea iterativă a metodei Heap de generare a permutărilor. Mi-a luat ceva timp să mă înșel, deoarece sursa de referință are o greșeală de tipar în algoritmul -_-.

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

Cu câteva exemple de timing pentru a număra anagramele „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 

Comentarii

• Acesta este de departe de departe câștigătorul, calculând 3.628.800 rezultate în ~5,000ms!
• Frumos! Ar trebui să precomputați dimensiunile matricei care vor da probabil rezultate și mai mari (deoarece anagramele și contorul sunt tablouri masive). Cred că voi încerca să trebuiască să iau o abordare distribuită pentru a o învinge pe aceasta 🙂
• Este ‘ interesant modul în care aceasta se scalează cu intrări de dimensiuni diferite jsperf.com/getanagramsc-r/2
• @megawac Aș fi interesat să vă văd abordarea după ce am folosit punctele forte ale acestei abordări.

Pe măsură ce lucram la o soluție mai bună, am descoperit o utilizare excelentă pentru noul Iteratoare JS & Generatoare , despre care am citit. Am petrecut probabil 6 ore astăzi jucându-mă cu această soluție și a fost merită fiecare minut. Aveți câteva erori de formatare, dar mă voi concentra complet pe performanță și voi părăsi formatarea către ceilalți recenzori.

---

Dacă rulați acest lucru împotriva unui cuvânt mare, vă va prăji aparatul

Ok, deci poate că și asta va merge puțin departe, dar serios, aceasta este o funcție costisitoare. Nu sunt un guru matematic, deci Am pus această întrebare pe Math.SE .

Formula pentru calcularea numărului de combinații posibile este extrem de abruptă:

Gândește-te astfel:

Câte alegeri ai pentru prima literă? Patru: 4_ _ _ _.

Pentru al doilea? Trei: 4⋅3 _ _.

Continuați astfel și găsiți că există 4⋅3⋅2⋅1 = 4! = 24 de alegeri în total. – MrRicci

Rularea funcției dvs. împotriva cuvântului „Enciclopedia” va avea ca rezultat o blocare a paginii dacă o rulați în partea clientului. Așadar, pentru a remedia problema, m-am gândit.

---

Fii cu mine – Acest lucru devine din ce în ce mai relevant pe măsură ce citești.

Am vrut să încerc să generez cuvinte reale (Distrează-mă cu codezul)

Un anagrama este un tip de joc de cuvinte, rezultatul rearanjării literelor unui cuvânt sau frază pentru a produce un cuvânt sau o frază nouă, folosind toate literele originale exact o dată – Wikipeda

Când mă gândesc la o anagramă, mă gândesc că rezultatul este cuvinte sau fraze reale . Acum, în timp ce scopul acestei revizuiri a codului nu este de a schimba funcționalitatea codului dvs., nu m-aș putea abține, dar nu vreau să mă distrez cu el. Așa că am decis să caut o soluție care să-mi permită să filtrez și să imprim orice cuvinte reale anagramele din rezultat.

Odată ce am urmărit în cele din urmă un șir de text simplu de ~ 130.000 de cuvinte în limba engleză pentru a le folosi ca listă de cuvinte, apoi trebuia să convertesc această listă în JS.Așa că am construit o funcție pentru a tăia șirul la fiecare spațiu și a imprima structura pentru un obiect cu proprietăți tastate, astfel încât să pot testa foarte rapid validitatea oricărui cuvânt prin worldList["word"] -> returns true if word is valid.

Imprimarea unei liste de 130.000 de cuvinte în corpul documentului ca șir JSON este, la fel ca funcția dvs., foarte scump.

---

… Și relevanța:

Deci, iată că problema dvs. se întâlnește cu cea pe care am inventat-o pentru mine. Cum procesați un buclă foarte scumpă fără blocarea unei pagini web?

În experimentarea posibilităților, am descoperit de fapt un mod de a permite funcției mele să gestionați 130.000 de cuvinte și funcția dvs. de a susține un cuvânt de orice dimensiune , echilibrând volumul de lucru în timp.

Buclele sunt uneori prea rapide pentru propriul lor bun

Buclele sunt făcute cât mai repede posibil, ceea ce este perfect pentru majoritatea a sarcinilor pentru care le folosim în paginile web. Dar dacă le cerem să se descurce prea mult, browserul nu se poate descurca.

Așa că am nevoie de o soluție care să-mi permită să distribui sarcina de lucru în timp, pentru a permite paginii să se descurce. bucle scumpe fără o problemă.

Soluția mea a fost să construiesc o buclă manuală printr-o funcție care se numea x ori, inserând un 1-2ms întârziere între iterații. Acest lucru a dat paginii suficient timp pentru a gestiona bucla , care, fără întârziere, a procesat cuvinte nebun de repede până la C înainte de a se prăbuși de fiecare dată. Acest lucru a funcționat excelent pentru generarea structurii listei de cuvinte JSON.

Dar o buclă întârziată a fost extrem de dificilă de implementat în funcția dvs. deja recursivă.

Mi-am dat seama atunci că aceasta este situația perfectă pentru a utiliza o soluție despre care am citit recent pentru JavaScript …

---

Iteratoare și generatoare JavaScript

Deci, aici vin Iteratoare JavaScript & Generatoare în ajutor.

Acum, această recenzie este deja un risc de a deveni un monstru, așa că, în loc să explic Generatori, voi „cita acest lucru va fi în curând un răspuns popular „s one-liner:

TL; DR: esența [folosirii unui] generator este controlul suspendării executării codului.

Și explicați pur și simplu că generatoarele sunt într-un mod îmbunătățit de implementare a iteratorilor.

Puteți citi restul pentru dvs. în răspunsul de acolo. În cazul în care acest răspuns nu o face pentru dvs., vă puteți îmbunătăți înțelegerea prin intermediul următoarelor resurse:

• Javascript Viitor: Generatoare

• Generatoare: o modalitate mai bună de a construi Iteratori

• Generatoare – MDN

• Cum se numește acest lucru generatori?

Acum, generatorii au un mare potențial în sarcina de a evita iadul de apel invers, dar vom merge la folosiți-le aici nu pentru formatarea structurii &, ci pentru performanță, care este (în opinia mea orientată spre performanță) motivul cel mai elegant pentru a le utiliza.

Nu sunt încă sigur dacă generatoarele sunt cea mai bună soluție aici, dar sunt „cea mai bună idee pe care o am, și acest lucru este o scuză pentru a le încerca.

---

Codul dvs. cu generatoare

Lucrul la această soluție încă. Ar trebui să funcționeze bine, pur și simplu nu am timp să termin încă și am vrut să ofer codul îmbunătățit mai devreme decât mai târziu. Voi posta această soluție în curând.

Actualizare: câteva zile mai târziu, nu am terminat învățarea generatoarelor, până la punctul de a putea scrie corect această funcție cu ei. Cu siguranță o voi posta aici imediat ce îmi voi da seama de sintaxa lor puțin mai bine.

---

Și, în sfârșit, întrucât generatoarele sunt noi și încă nu sunt acceptate peste tot .. O versiune îmbunătățită a codului dvs. fără ele

Notă: practicile mele de formatare sunt, în general, propria mea lizibilitate preferință în loc de cele mai bune practici. Nu vă simțiți obligat să vă formatați codul în acest fel.

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

Prin declararea variabilelor în afara buclelor, economisim semnificativ, ca veți vedea în rezultate. De asemenea, cred că word.slice() a funcționat puțin mai bine decât word.substr(). între cele două optimizări, acest cod efectuează be mai mic decât codul dvs. original.

---

Și nu în ultimul rând, rezultatele sunt rezultate!

Cod original : Rezultate actualizate! Pagina nu se blochează fără înregistrare.

• „cod”, 4 caractere: 24 rezultate , ~ 1ms
• „coder”, 5 caractere: 120 rezultate , ~ 1ms
• „codere”, 6 caractere: 720 rezultate , ~ 6ms
• „coderev”, 7 caractere: 5040 rezultate , ~ 11ms
• „coderevi”, 8 caractere: 40.320 rezultate , ~ 75ms
• „coderevie”, 9 caractere: 362.880 rezultate , pagina eșuează
• „codereview”, 10 caractere: 3.628.800 rezultate , pagina eșuează

Cod îmbunătățit : Rezultate actualizate – Pagina nu se blochează fără înregistrare.

• ” cod „, 4 caractere: 24 de rezultate , ~ 0.5ms
• ” coder „, 5 caractere: 120 rezultate , ~ 0.5ms
• „codere”, 6 caractere: 720 rezultate , ~ 1.5ms
• „coderev”, 7 caractere: 5040 rezultate , ~ 8ms
• ” coderevi „, 8 caractere: 40.320 rezultate , ~ 53ms
• ” coderevie „, 9 caractere: 362.880 rezultate , ~ 556ms
• „codereview”, 10 caractere: 3.628.800 rezultate , ~ 12725ms

În timp real cu generatoare

(Codul nu este complet – Generatoarele se dovedesc puțin dificile)

Am folosit console.time() pentru a realiza măsurători precise până la cea mai apropiată milisecundă, finalizând 3-5 încercări fiecare și estimând o medie generală bazată pe r esultă. Desigur, aceste rezultate vor varia de la o mașină la alta. Timpul comparații este cheia citirii parametrilor de referință, nu a vitezei.

---

Tl; Dr Summary, așa cum a promis

Buclele sunt extrem de puternice instrument în programare, dar nu se ocupă bine de un număr mare de iterații scumpe în browserul web. Funcții scumpe de buclare ca aceasta funcționează perfect, totuși, dacă distribuiți sarcina de lucru în timp. Un mod interesant de a face acest lucru este să folosiți JS Generators , o jucărie nouă disponibilă astăzi în magazinele web, dar nu neapărat pe piețele locale, așa că utilizați cu grijă până când JS 2.0 este implementat pe scară mai largă! Utilizând puterea generatoarelor JS, putem gestiona procese costisitoare de lungă durată fără a vedea probleme de performanță.

Comentarii

• ți-ai dat seama vreodată de generatoare?
• @megawac Am petrecut multe ore pe el, fără suficiente ghiduri / informații / tutoriale pentru a-mi da seama cum să o fac. I ‘ am cheltuit cât timp am liber în fiecare zi de la acest post pentru a le studia, dar … nu ‘ nu învăț repede din documentația brută. Cunoașteți resurse bune pentru generatoare și iteratoare?
• Sună ca un fir de stivuire bun @ jt0dd
• Am scris un rezolvator pentru ziarul local ‘ puzzle Jumble. Am avut o listă de 600.000 de cuvinte scrabble pe care le-am prelucrat în prealabil pentru a sorta literele din fiecare cuvânt. Apoi am făcut același lucru pentru literele de căutare și am încercat să găsesc cuvinte. Poate căuta toate cuvintele cuprinse între 4 și 10 litere cu 10 litere în milisecunde. Literele ‘ puls ‘ introduse în orice ordine rezultă în ‘ bhort ‘ care se conectează direct la ‘ throb ‘ și ‘ bulion ‘, nu este nevoie să încercați fiecare combinație. De exemplu, dacă căutați 4 litere cu 5 litere, există doar 4 combinații atunci când literele sunt sortate, 120 dacă nu.
• @ jt0dd I ‘ m confuz despre utilizarea cuvântului.lungime + 1 când se folosește felie. Puteți explica, vă rog?

Am aruncat o privire asupra codului @ jt0dd și m-am întrebat cum ar putea rezolva mai multe cazuri. Vă spun, permiteți să adăugați un strat de cache și să precomputați lungimile matricelor rezultate!

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 ” e urât! Sper că tot timpul nu a fost pentru nimic …

Hash-uri precomputate

• „cod”, 4 caractere: 24 rezultate , < = 1ms
• „coder”, 5 caractere: 120 rezultate , < = 1ms
• „codere”, 6 caractere: 720 rezultate , < = 1ms
• „coderev”, 7 caractere: 5040 rezultate , < = 3ms
• ” coderevi „, 8 caractere: 40.320 rezultate , < = 18ms
• „coderevie”, 9 caractere: 362.880 rezultate , 135ms
• „codereview”, 10 caractere: 3.628.800 rezultate , 2.1 s

Whoopy, am întâmpinat provocarea. Să vedem cât de mult putem merge mai departe. codereview este un cuvânt greu doar duplicat e caractere. Să încercăm ceva mai ușor pentru următoarea go. Haideți să încercăm "anagramarmy"

… … …

Bine, am bătut mai mult decât poate browserul meu să mestece se pare, 40 de milioane de permutări de șiruri par a fi dincolo de limită 🙁

Veți observa că am reproiectat algoritmul pentru a evita depășirea stivei – căutările ar trebui făcute în afara recursiunii.

Putem crește șansa ca algoritmul nostru să nu se blocheze făcându-l asincron și făcând fiecare cuvânt 100,000 elemente la fiecare milisecundă pentru a evita oprirea.

Comentarii

• Minunat! Acest lucru este mult mai bun decât versiunea generatorului pe care ‘ m lucrez. +1 ( Acest răspuns ar trebui acceptat, ‘ va fi cu mult mai eficient decât soluția mea generatoare.)
• Brilliant … Doar genial. ca aceasta. Când termin soluția de generare a armoniei în timp real (sau poți să o implementezi pe a ta), nu ezita să iei asta și să faci același lucru cu ea. ‘ va fi mai lent, dar va întoarce rezultatele în timp real și nu va avea sfârșitul cât de mare poate fi un cuvânt.
• ahh, mjolka ne învinge ambele de far .
• Bună ziua, cum execut acest cod de-a lungul html și css din domeniul meu? ‘ folosesc acest lucru gratuit: morsetovoynich.000webhostapp.com

Am realizat două scripturi:

1. Primul este rapid, dar nu poate ține mult;
2. Al doilea este lent, dar poate afișa rezultate nelimitate.

Ambele folosesc prototipul realizat de mine: fastPush, fastSplit și fastJoin; care sunt mai rapide decât metoda standard split și join. utilizați bitwise pentru a verifica dacă este impar sau par, pentru că știu că mod este cea mai lentă operație posibilă pe un computer.

Primul script bate cel mai rapid rezultat al celorlalți cu peste 750 ms (pe medie) pe 10chars provocare de permutare .

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

Oricum acest prim program are o limită și rupe pagina dacă încercați mai mult de 10 caractere.

Al doilea program ( una de mai jos) folosește o funcție de autoinvocare și se conectează la bucățile de consolă de 4e4 elemente, șterge matricea de anagrame de fiecare dată când scoate o bucată și, de asemenea, șterge co nsole.log fiecare 5 bucăți (suficient pentru a vă permite să vedeți acele combinații). Pentru a invoca automat funcția, programul folosește setZeroTimeout ( blogul lui David Baron ) în loc de setTimeout, deoarece setTimeout este mult mai lent.

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

O altă variantă (scrisă i C) folosind un contor simplu peste Set de alimentare al tuturor șirurilor.

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

Executați cu tipărirea tuturor șirurilor:

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

Comentarii

• Ce vrei să spui prin ” tipărirea tuturor șirurilor „? Funcția dvs. afișează doar părți ale cuvântului, de exemplu, dacă rulați anagramele abc`, ieșiți a,b,ab,c,ac,bc,abc

Matrice tipizate pentru o performanță mai bună.

Folosind metoda răspunsurilor acceptate puteți tripla performanța.

Rularea răspunsului câștigător pe mașina mea a oferit valori comparative

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

Și atunci când se utilizează t matrici yped

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

pentru creșterea performanței de 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; } 

Pentru a îmbunătăți puțin mai mult puteți predefini matricea de rezultate pentru a obține

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

Pentru a o îmbunătăți de până la 3,95 ori mai rapid decât răspunsul câștigător.