Genera tutte le possibili combinazioni di lettere in una parola

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

Lancio il cappello sul ring con la versione iterativa del metodo Heap per generare permutazioni. Mi ci è voluto un po per ottenere il risultato corretto, poiché la mia sorgente di riferimento ha un errore di battitura nellalgoritmo -_-.

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

Con alcuni esempi di tempo per contare gli anagrammi di “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 

Commenti

• Questo è di gran lunga il vincitore, calcolando 3.628.800 risultati in ~5.000 ms!
• Bene! Dovresti precalcolare le dimensioni dellarray probabilmente produrrà risultati ancora maggiori (poiché anagrammi e contatore sono array enormi). Penso che proverò a dover adottare un approccio distribuito per battere questo 🙂
• È ‘ interessante come questo scala con input di dimensioni diverse jsperf.com/getanagramsc-r/2
• @megawac Sarei interessato a vedere il tuo approccio dopo aver utilizzato i punti di forza di questo approccio.

Mentre lavoravo a una soluzione migliore, ho trovato un ottimo utilizzo per il nuovo JS Iterators & Generators , di cui ho “letto”. Ho passato probabilmente 6 ore oggi a giocherellare con questa soluzione, ed è stato vale ogni minuto. Hai alcuni errori di formattazione, ma mi concentrerò completamente sulle prestazioni e lascerò la formattazione agli altri revisori.

---

Eseguire questo contro una parola grossa friggerà la tua macchina

Ok, forse anche questo piccolo lontano, ma seriamente, questa è una funzione costosa. Non sono un guru della matematica, quindi Ho posto questa domanda su Math.SE .

La formula per calcolare il numero di possibili combinazioni è estremamente ripida:

Pensala in questo modo:

Quante scelte hai per la prima lettera? Quattro: 4_ _ _ _.

Per il secondo? Tre: 4⋅3 _ _.

Continua così e troverai 4 there3⋅2⋅1 = 4! = 24 scelte in totale. – MrRicci

Esegui la tua funzione contro la parola “Encyclopedia” provocherà un arresto anomalo della pagina se lo esegui sul lato client. Quindi, per risolvere il problema, ho pensato un po .

---

Abbi pazienza: questo diventa sempre più rilevante man mano che leggi.

Volevo provare a generare parole reali (divertendomi con il codez)

Un lanagramma è un tipo di gioco di parole, il risultato della riorganizzazione delle lettere di una parola o frase per produrre una nuova parola o frase, utilizzando tutte le lettere originali esattamente una volta – Wikipeda

Quando penso a un anagramma, penso che il risultato sia parole o frasi reali . Ora, mentre lo scopo di questa revisione del codice non è quello di cambiare la funzionalità del tuo codice, non ho potuto fare a meno di divertirmi un po con esso. Quindi ho deciso di cercare una soluzione che mi permettesse di filtrare e stampare qualsiasi parola reale anagrammi dal risultato.

Dopo aver finalmente rintracciato una stringa di testo normale di ~ 130.000 parole inglesi da utilizzare come elenco di parole, quindi ho dovuto convertire questo elenco in JS.Quindi ho creato una funzione per suddividere la stringa in ogni spazio e stampare la struttura di un oggetto con proprietà con chiave, in modo da poter verificare molto rapidamente la validità di qualsiasi parola tramite worldList["word"] -> returns true if word is valid.

Stampare un elenco di 130.000 parole nel corpo del documento come stringa JSON è, come la tua funzione, molto costoso.

---

… E la pertinenza:

Ecco dove il tuo problema incontra quello che ho inventato per me stesso. Come elabori un loop molto costoso senza bloccare una pagina web?

Sperimentando le possibilità, ho effettivamente scoperto un modo per consentire alla mia funzione di gestire 130.000 parole e la tua funzione per sostenere una parola di qualsiasi dimensione , bilanciando il carico di lavoro nel tempo.

I cicli a volte sono troppo veloci per il loro bene

I loop sono fatti per essere il più veloci possibile, il che è perfetto per la maggior parte delle attività per cui li usiamo nelle pagine web. Ma se chiediamo loro di gestire troppo, il browser non può gestirlo.

Quindi avevo bisogno di una soluzione che mi permettesse di distribuire il carico di lavoro nel tempo, in modo da consentire alla pagina di gestire loop costosi senza problemi.

La mia soluzione era creare un loop manuale tramite una funzione che si chiamava x volte, inserendo 1-2ms ritardo tra le iterazioni. Questo ha dato alla pagina tempo sufficiente per gestire il ciclo , che, senza ritardo, elaborava le parole follemente veloce fino alle C prima di schiantarsi ogni volta. Ha funzionato benissimo per generare la mia struttura dellelenco di parole JSON.

Ma un ciclo ritardato era estremamente difficile da implementare nella tua funzione già ricorsiva.

Mi sono reso conto che questa è la situazione perfetta per utilizzare una soluzione di cui ho letto di recente per JavaScript …

---

Iteratori e generatori JavaScript

Quindi, ecco che arrivano JavaScript Iteratori & Generatori in soccorso.

Ora, questa recensione è già un rischio di diventare un mostro, quindi invece di spiegare Generators, citerò questa risposta che presto sarà popolare “s one-liner:

TL; DR: lessenza di [usare un] generatore è controllare la sospensione dellesecuzione del codice.

E spiega semplicemente che i generatori sono in un modo migliore per impiantare gli iteratori.

Puoi leggere il resto da solo nella risposta qui. Se questa risposta non funziona per te, puoi migliorare la tua comprensione tramite le seguenti risorse:

• Javascript “s Futuro: generatori

• Generatori: un modo migliore per creare iteratori

• Generatori – MDN

• Come si chiama questa cosa generatori?

Ora, i generatori hanno un grande potenziale nel compito di evitare linferno di richiamata, ma “stiamo andando a usarli qui non per la formattazione della struttura &, ma per le prestazioni, che è (a mio parere parziale sulle prestazioni) il motivo più elegante per usarli.

Non sono ancora sicuro che i generatori siano la soluzione migliore qui, ma sono lidea migliore che ho, e questa è una scusa per provarli.

---

Il tuo codice con i generatori

Lavorando su questa soluzione ancora. Dovrebbe funzionare bene, semplicemente non ho ancora il tempo di finire e volevo offrire il codice migliorato il prima possibile. Pubblicherò presto questa soluzione.

Aggiornamento: pochi giorni in seguito, non ho finito di imparare i generatori, al punto da essere in grado di scrivere correttamente questa funzione con loro. Lo posterò sicuramente qui non appena avrò capito un po meglio la loro sintassi.

---

E infine, poiché i generatori sono nuovi e non sono ancora supportati ovunque .. Una versione migliorata del tuo codice senza di essi

Nota: le mie pratiche di formattazione sono generalmente di mia leggibilità preferenza piuttosto che best practice. Non sentirti obbligato a formattare il tuo codice in questo modo.

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

Dichiarando variabili al di fuori dei cicli, salviamo in modo significativo, poiché vedrai nei risultati. Inoltre, credo che word.slice() abbia funzionato leggermente meglio di word.substr(). Tra le due di queste ottimizzazioni, questo codice esegue essere tter del codice originale.

---

E ultimo ma non meno importante, i risultati delle prestazioni!

Codice originale : risultati aggiornati! La pagina non si blocca senza registrazione.

• “codice”, 4 caratteri: 24 risultati , ~ 1 ms
• “coder”, 5 caratteri: 120 risultati , ~ 1 ms
• “codere”, 6 caratteri: 720 risultati , ~ 6 ms
• “coderev”, 7 caratteri: 5040 risultati , ~ 11 ms
• “coderevi”, 8 caratteri: 40.320 risultati , ~ 75 ms
• “coderevie”, 9 caratteri: 362.880 risultati , errore di pagina
• “codereview”, 10 caratteri: 3.628.800 risultati , errore di pagina

Codice migliorato : risultati aggiornati – La pagina non si arresta in modo anomalo senza registrazione.

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

Tempo reale con generatori

(Codice non completo – I generatori si stanno rivelando un po difficili)

Ho usato console.time() per ottenere misurazioni accurate al millisecondo più vicino, completando 3-5 prove ciascuna e stimando una media generale basata su r esulti. Questi risultati ovviamente varieranno da macchina a macchina. I confronti del tempo sono la chiave per leggere i benchmark, non le velocità.

---

Tl; Dr Riepilogo, come promesso

I loop sono un estremamente potente strumento di programmazione, ma non gestiscono bene numeri mostruosi di costose iterazioni nel browser web. Le costose funzioni di looping come questa funzionano perfettamente, tuttavia, se distribuisci il carico di lavoro nel tempo. Un modo interessante per farlo è usare JS Generators , un nuovo giocattolo disponibile oggi nei negozi web, ma non necessariamente nei mercati locali, quindi usalo con cautela fino a quando JS 2.0 non sarà più ampiamente implementato! Utilizzando la potenza dei generatori JS, siamo in grado di gestire processi costosi di lunga durata senza riscontrare problemi di prestazioni.

Commenti

• hai mai scoperto i generatori?
• @megawac Ci ho passato molte ore, senza abbastanza guide / informazioni / tutorial per capire davvero come farlo. I ‘ ho speso tutto il tempo che ho a disposizione ogni giorno da questo post per studiarli, ma … ‘ t imparo velocemente dalla documentazione grezza. Conosci qualche buona risorsa su generatori e iteratori?
• Sembra un buon thread di stackoverflow @ jt0dd
• Ho scritto un risolutore per il giornale locale ‘ s Jumble puzzle. Avevo un elenco di 600.000 parole scrabble che ho preelaborato per ordinare le lettere in ogni parola. Poi ho fatto lo stesso per le lettere di ricerca e ho cercato di trovare le parole. Potrebbe eseguire la scansione di tutte le parole comprese tra 4 e 10 lettere date 10 lettere in millisecondi. Le lettere ‘ throb ‘ immesse in qualsiasi ordine risultano in ‘ bhort ‘ che collega direttamente a ‘ throb ‘ e ‘ brodo ‘, non è necessario provare ogni combinazione. Ad esempio, se si cercano parole di 4 lettere con 5 lettere, ci sono solo 4 combinazioni quando le lettere sono ordinate, 120 in caso contrario.
• @ jt0dd I ‘ sono confuso sulluso di word.length + 1 quando si usa slice. Puoi spiegare per favore?

Ho dato unocchiata al codice di @ jt0dd e mi sono chiesto come potrebbe gestire altri casi. Te lo dico io, aggiungiamo un livello di cache e calcoliamo in anticipo le lunghezze degli array risultanti!

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 ” è brutto! Spero che tutto quel tempo non sia stato per niente …

Hash precalcolati

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

Whoopy, abbiamo vinto la sfida. Vediamo quanto possiamo andare oltre. codereview è una parola difficile che duplica solo e caratteri. Proviamo qualcosa di più semplice per il prossimo vai. Proviamo "anagramarmy"

… … …

Ok, ho morso più di quanto il mio browser possa masticare a quanto pare, 40 milioni di permutazioni di stringhe sembrano essere oltre il limite 🙁

Noterai che ho ridisegnato lalgoritmo per evitare loverflow dello stack: le ricerche dovrebbero essere fatte al di fuori della ricorsione.

Possiamo aumentare la possibilità che il nostro algoritmo non vada in crash rendendolo asincrono ed eseguendo ogni elemento di 100,000 ogni millisecondo per evitare larresto.

Commenti

• Fantastico! È molto meglio della versione del generatore su cui ‘ sto lavorando. +1 ( Questa risposta dovrebbe essere accettata, ‘ sarà di gran lunga più efficiente della mia soluzione generatore.)
• Fantastico … Semplicemente fantastico. come questo. Quando avrò finito la soluzione del generatore di armonie in tempo reale (o potresti implementare la tua), sentiti libero di prenderla e fare lo stesso con essa. ‘ sarà più lento, ma restituirà risultati in tempo reale e non avrà fine alla grandezza di una parola che può gestire.
• ahh, mjolka ci ha battuti entrambi da far .
• Salve, come faccio a eseguire questo codice insieme a html e css allinterno del mio dominio? ‘ sto usando questo gratuito: morsetovoynich.000webhostapp.com

Ho creato due script:

1. Il primo è veloce ma non può contenere molto;
2. Il secondo è lento ma può mostrare risultati illimitati.

Entrambi usano il prototipo che ho realizzato: fastPush, fastSplit e fastJoin; che sono più veloci del metodo standard split and join. Entrambi anche usa bit a bit per verificare se dispari o pari, perché so che mod è loperazione più lenta possibile su un computer.

Il primo script batte il risultato più veloce degli altri di oltre 750 ms (in media) con la sfida di permutazione a 10 caratteri .

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

Comunque questo primo programma ha un limite e rompe la pagina se provi più di 10 caratteri.

Il secondo programma (il uno sotto) utilizza una funzione di auto invocazione e accede ai blocchi della console di elementi 4e4, cancella larray degli anagrammi ogni volta che emette un blocco e cancella anche co nsole.log ogni 5 blocchi (abbastanza per farti vedere quelle combinazioni). Per invocare autonomamente la funzione, il programma utilizza setZeroTimeout ( blog di David Baron “) invece di setTimeout perché setTimeout è molto più lento.

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

Ancora unaltra variante (scritta i C) utilizzando un semplice contatore su Power Set di tutte le stringhe.

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

Esegui con stampa di tutte le stringhe:

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

Commenti

• Cosa intendi con ” stampa di tutte le stringhe “? La tua funzione restituisce solo parti della parola, ad esempio se run` anagrammi abc` restituisce a,b,ab,c,ac,bc,abc

Array tipizzati per prestazioni migliori.

Utilizzando il metodo delle risposte accettato puoi triplicare le prestazioni.

Lesecuzione della risposta vincente sulla mia macchina ha fornito un benchmark

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

E quando si utilizza t array yped

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

per un aumento delle prestazioni di 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; } 

Per migliorare un po di più puoi predefinire larray dei risultati per ottenere

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

per migliorarlo fino a 3,95 volte più veloce della risposta vincente.