Generování všech možných kombinací písmen ve slově

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

Chystám se hodit svůj klobouk do ringu s iterativní verzí haldy s metodou generování permutací. Chvíli mi trvalo, než jsem se dostal do pořádku, protože můj referenční zdroj má překlep v algoritmu -_-.

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

S některými ukázkovými načasováními pro počítání přesmyček „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 

Komentáře

• Toto je zdaleka vítěz, počítá se 3 628 800 výsledků za ~5 000 ms !
• Skvělé! Měli byste předem vypočítat, že velikosti pole pravděpodobně přinesou ještě lepší výsledky (protože přesmyčky a čítače jsou masivní pole). Myslím, že se pokusím porazit tohle tím, že budu muset použít distribuovaný přístup 🙂
• Je to ‚ zajímavé, jak to škáluje vstupy různých velikostí jsperf.com/getanagramsc-r/2
• @megawac Rád bych viděl váš přístup po využití silných stránek tohoto přístupu.

Jak jsem pracoval na lepším řešení, přišel jsem na skvělé využití nového JS Iterators & generátory , o kterých jsem četl. Strávil jsem dnes asi 6 hodin fidlováním s tímto řešením a bylo to stojí za každou minutu. Dostali jste nějaké chyby formátování, ale se zaměřím úplně na výkon a nechám formátování ostatním recenzentům.

---

Pokud to spustíte proti velkému slovu, váš počítač to smaží

Dobře, takže možná to bude trochu daleko, ale vážně, toto je drahá funkce. nejsem žádný matematický guru, takže Tuto otázku jsem položil na Math.SE .

Vzorec pro výpočet počtu možných kombinací je extrémně strmý:

Přemýšlejte o tom takto:

Kolik možností máte pro první písmeno? Čtyři: 4_ _ _ _.

Za druhé? Tři: 4⋅3 _ _.

Pokračujte takto a zjistíte, že máte celkem 4⋅3⋅2⋅1 = 4! = 24 možností. – MrRicci

Spuštění funkce proti slovu Encyklopedie bude mít za následek definitivní zhroucení stránky, pokud ji spustíte na straně klienta. Abych to napravil, přemýšlel jsem.

---

Mějte se mnou – to bude při čtení čím dál důležitější.

Chtěl jsem zkusit generovat skutečná slova (pobavit se s codezem)

An anagram je typ slovní hříčky, výsledkem přeskupení písmen slova nebo fráze tak, aby vzniklo nové slovo nebo fráze, přičemž se všechna původní písmena použijí přesně jednou – Wikipeda

Když pomyslím na anagram, myslím, že výsledkem budou skutečná slova nebo fráze. I když účel této kontroly kódu není změnit funkčnost vašeho kódu, nemohl jsem si pomoct, ale chci se s tím pobavit. Rozhodl jsem se tedy hledat řešení, které by mi umožnilo odfiltrovat a vytisknout z výsledku jakékoli skutečné slovní přesmyčky.

Jakmile jsem konečně vystopoval prostý textový řetězec ~ 130 000 anglických slov , které mohu použít jako seznam slov, jsem pak potřeboval tento seznam převést na JS.Postavil jsem tedy funkci na rozříznutí řetězce v každém prostoru a vytištění struktury objektu s vlastnostmi s klíčem, abych mohl velmi rychle otestovat platnost jakéhokoli slova pomocí worldList["word"] -> returns true if word is valid.

Tisk seznamu 130 000 slov do těla dokumentu jako řetězec JSON je, stejně jako vaše funkce, velmi drahý.

---

… A relevance:

Takže tady se setkává váš problém s problémem, který jsem si sám vymyslel. Jak zpracováváte velmi nákladná smyčka bez zhroucení webové stránky?

Při experimentování s možnostmi jsem vlastně objevil způsob, jak umožnit mé funkci zvládněte 130 000 slov a svou funkcí udržujte slovo jakékoli velikosti vyvážením pracovní zátěže v čase.

Smyčky jsou někdy příliš rychlé pro vlastní dobro

Smyčky jsou vytvářeny tak, aby byly co nejrychlejší, což je pro většinu úkolů, na které je používáme na webových stránkách. Pokud je ale požádáme, aby toho zvládli příliš mnoho, prohlížeč to nezvládne.

Takže jsem potřeboval řešení, které by mi umožnilo rozložit pracovní zátěž v čase, aby mohla stránka zpracovat drahé smyčky bez problému.

Mým řešením bylo vytvořit ruční smyčku pomocí funkce, která se x krát s vložením 1-2ms zpoždění mezi iteracemi. To poskytlo stránce dostatek času na zpracování smyčky , která bez zpoždění zpracovávala slova šíleně rychle až do C, než pokaždé spadne. To fungovalo skvěle pro generování mé struktury seznamu slov JSON.

Implementace zpožděné smyčky ve vaší již rekurzivní funkci však byla extrémně složitá.

Tehdy jsem si uvědomil, že toto je ideální situace pro využití řešení, o kterém jsem nedávno četl pro JavaScript …

---

Iterátory a generátory JavaScriptu

Takže zde přicházejí Iterátory JavaScriptu & Generátory na záchranu.

Tato recenze již nyní představuje riziko, že se z vás stane monstrum, takže místo vysvětlování generátorů budu brzy citovat tuto brzy populární odpověď „s one-liner:

TL; DR: podstata [pomocí a] generátoru je řízení pozastavení provádění kódu.

A jednoduše vysvětlete, že generátory vylepšeným způsobem implementují iterátory.

Zbytek si můžete přečíst sami v odpovědi. Pokud to pro vás tato odpověď docela nejde, můžete své porozumění vylepšit pomocí následujících zdrojů:

• Javascript Budoucnost: Generátory

• Generátory: lepší způsob vytváření iterátorů

• Generátory – MDN

• Co je to, co se nazývá generátory?

Nyní mají generátory velký potenciál vyhnout se peklu zpětného volání, ale my se chystáme nepoužívejte je zde ne k formátování & struktury, ale k výkonu, což je (podle mého názoru zkreslený výkon) nejelegantnějším důvodem k jejich použití.

Ještě si nejsem jistý, zda jsou zde generátory nejlepším řešením, ale jsou to nejlepší nápady, které mám, a to je výmluvou, abychom je mohli vyzkoušet.

---

Váš kód s generátory

Práce na toto řešení stále. Mělo by to fungovat dobře, zatím nemám čas na dokončení a chtěl jsem nabídnout vylepšený kód dříve než později. Toto řešení zveřejním brzy.

Aktualizace: O několik dní Později jsem nedokončil učení generátorů, takže jsem s nimi dokázal tuto funkci správně zapsat. Určitě to sem pošlu, jakmile zjistím jejich syntaxi o něco lépe.

---

A konečně, protože Generátory jsou nové a zatím nejsou podporovány všude .. Vylepšená verze vašeho kódu bez nich

Poznámka: Moje postupy formátování jsou obecně moje vlastní čitelnost raději než osvědčené postupy. Necítí se povinnost formátovat váš kód tímto způsobem.

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

Deklarováním proměnných mimo smyčky významně ukládáme, protože uvidíte ve výsledcích. Také se domnívám, že word.slice() si vedl o něco lépe než word.substr(). mezi těmito dvěma optimalizacemi, tímto kódem provádí být než váš původní kód.

---

A v neposlední řadě výsledky přinášejí výkon!

Původní kód : Výsledky byly aktualizovány! Stránka se nezdaří bez přihlášení.

• „code“, 4 znaky: 24 výsledků , ~ 1ms
• „coder“, 5 znaků: 120 výsledků , ~ 1ms
• „codere“, 6 znaků: 720 výsledků , ~ 6ms
• „coderev“, 7 znaků: 5040 výsledků , ~ 11ms
• „coderevi“, 8 znaků: 40 320 výsledků , ~ 75 ms
• „coderevie“, 9 znaků: 362 880 výsledků , selhání stránky
• „codereview“, 10 znaků: 3 628 800 výsledků , selhání stránky

Vylepšený kód : Výsledky aktualizovány – stránka se bez přihlášení nezdaří.

• “ code „, 4 znaky: 24 výsledků , ~ 0,5 ms
• “ coder „, 5 znaků: 120 výsledků , ~ 0,5ms
• „codere“, 6 znaků: 720 výsledků , ~ 1,5ms
• „coderev“, 7 znaků: 5040 výsledků , ~ 8ms
• “ coderevi „, 8 znaků: 40 320 výsledků , ~ 53 ms
• “ coderevie „, 9 znaků: 362 880 výsledků , ~ 556ms
• „codereview“, 10 znaků: 3 628 800 výsledků , ~ 12725 ms

v reálném čase s generátory

(Kód není úplný – generátory se ukazují jako obtížné)

Použil jsem console.time() dosáhnout měření s přesností na nejbližší milisekundu, absolvovat každý 3 až 5 pokusů a odhadnout obecný průměr na základě r dospělí. Tyto výsledky se samozřejmě budou u jednotlivých strojů lišit. Klíčem ke čtení srovnávacích testů jsou časové srovnání , nikoli rychlosti.

---

Tl; Dr Summary, jak jsem slíbil

Smyčky jsou extrémně silné nástroj v programování, ale ve webovém prohlížeči dobře nezvládají počty drahých iterací. Drahé smyčkové funkce, jako je tato, fungují perfektně, pokud však rozložíte pracovní zátěž v čase. Jedním zajímavým způsobem, jak to udělat, je použití generátorů JS , nová hračka dostupná v dnešních webových obchodech, ale nemusí to být nutně na místních trzích, proto používejte opatrně, dokud nebude JS 2.0 široce implementován! Využitím síly generátorů JS, dokážeme spravovat dlouhotrvající drahé procesy, aniž bychom viděli problémy s výkonem.

Komentáře

• už jste někdy zjistili generátory?
• @ megawac Strávil jsem na tom mnoho hodin, bez dostatečných průvodců / informací / tutoriálů, abych skutečně přišel na to, jak to udělat. I ‚ utrácel jsem tolik času, kolik mám od tohoto příspěvku každý den zdarma, abych je mohl prostudovat, ale … ze surové dokumentace se rychle neučím ‚. Znáte nějaké dobré zdroje na generátorech a iterátorech?
• Zní to jako dobré vlákno stackoverflow @ jt0dd
• Napsal jsem řešitele pro místní papír ‚ s Jumble puzzle. Měl jsem seznam 600 000 scrabble slov, která jsem předem zpracoval, abych roztřídil písmena v každém slově. Pak jsem udělal totéž pro hledaná písmena a pokusil se najít slova. Mohlo by skenovat všechna slova mezi 4 a 10 písmeny a 10 písmen v milisekundách. Písmena ‚ throb ‚ zadaná v libovolném pořadí mají za následek ‚ bhort ‚ který odkazuje přímo na ‚ throb ‚ a ‚ broth ‚, není třeba zkoušet každou kombinaci. Například pokud hledáte 4písmenná slova s 5 písmeny, existují pouze 4 kombinace, když jsou písmena tříděna, 120 pokud ne.
• @ jt0dd I ‚ m zmatená o použití word.length + 1 při použití řezu. Můžete mi to prosím vysvětlit?

Podíval jsem se na kód @ jt0dd a přemýšlel, jak jsme zvládne i další případy. Řeknu vám, přidejte vrstvu mezipaměti a předem vypočítejte délky výsledných polí!

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

Muž, že “ je ošklivý! Doufám, že ten čas nebyl k ničemu …

Předpočítané hodnoty hash

• „code“, 4 znaky: 24 výsledků , < = 1ms
• „coder“, 5 znaků: 120 výsledků , < = 1ms
• „codere“, 6 znaků: 720 výsledků , < = 1ms
• „coderev“, 7 znaků: 5040 výsledků , < = 3ms
• “ coderevi „, 8 znaků: 40 320 výsledků , < = 18ms
• „coderevie“, 9 znaků: 362 880 výsledků , 135ms
• „codereview“, 10 znaků: 3 628 800 výsledků , 2,1 s

Whoopy, my jsme tuto výzvu splnili. Podívejme se, o kolik ještě můžeme jít. codereview je tvrdé slovo, pouze duplicitní e znaky. Zkusme něco jednoduššího pro další jdi. Zkusme "anagramarmy"

… … …

Dobře, odhryzl jsem víc, než dokáže můj prohlížeč žvýkat zdá se, 40 milionů řetězcových permutací se zdá být nad limit 🙁

Všimnete si, že jsem přepracoval algoritmus, aby nedocházelo k přetečení zásobníku – vyhledávání by mělo být prováděno mimo rekurzi.

Můžeme zvýšit pravděpodobnost selhání našeho algoritmu tím, že ho provedeme asynchronním a každou milisekundu uděláme 100,000 prvky, abychom zabránili zastavení.

Komentáře

• Úžasné! Je to mnohem lepší než na generátorové verzi, na které ‚ pracuji. +1 ( Tuto odpověď je třeba přijmout, ‚ bude mnohem efektivnější než moje generátorové řešení.)
• Brilantní … Brilantní. Opravdu takhle. Až dokončím řešení generátoru harmonie v reálném čase (nebo můžete implementovat vlastní), klidně si to vezměte a udělejte to samé. ‚ Bude pomalejší, ale vrátí výsledky v reálném čase a nebude mít konec toho, jaké velké slovo zvládne.
• ach, mjolka nás porazila obojí far .
• Ahoj, jak provedu tento kód podél vedlejších html a css v mé doméně? ‚ m používám tento bezplatný: morsetovoynich.000webhostapp.com

Vytvořil jsem dva skripty:

1. První je rychlý, ale moc toho neudrží;
2. Druhá je pomalá, ale může ukázat neomezené výsledky.

Oba používají prototyp, který jsem vytvořil: fastPush, fastSplit a fastJoin; které jsou rychlejší než standardní metoda split and join. Oba také pomocí bitů zkontrolujte, zda je liché nebo sudé, protože vím, že mod je nejpomalejší operace v počítači.

První skript překonává nejrychlejší výsledek ostatních o více než 750 ms (průměrně) při výzvě permutace na 10 znaků .

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

Každopádně tento první program má limit a stránku rozbije, pokud zkusíte více než 10 znaků.

Druhý program ( jeden níže) používá funkci samovolného vyvolání a přihlašuje se ke konzolovým blokům prvků 4e4, vymaže pole anagramů pokaždé, když vydá blok, a také vymaže co nsole.log každých 5 bloků (dost na to, abyste viděli tyto kombinace). K vlastnímu vyvolání funkce program používá setZeroTimeout ( blog Davida Barona ) místo setTimeout, protože setTimeout je mnohem pomalejší.

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

Ještě další varianta (napsaná i C) pomocí jednoduchého počítadla přes Power Set všech řetězců.

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

Spustit s tiskem všech řetězců:

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

Komentáře

• Co myslíte pod “ tiskem všech řetězců „? Vaše funkce vypisuje pouze části slova, např. pokud run` anagrams abc` výstupy a,b,ab,c,ac,bc,abc

Typizovaná pole pro lepší výkon.

Použitím metody přijatých odpovědí můžete výkon ztrojnásobit.

Spuštění vítězné odpovědi na mém stroji dalo srovnatelné

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

A při použití t yped pole

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

pro zvýšení výkonu o 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; } 

Chcete-li trochu více výsledné pole můžete předdefinovat, abyste získali

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

Vylepšit jej až 3,95krát rychleji než vítězná odpověď.