Generáljon minden lehetséges betűkombinációt egy szóban

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

A kalapomat a ringbe dobom a Heap módszer iteratív változatával, amely permutációk generálására szolgál. Nekem eltartott egy ideig, amíg rendbe jöttem, mivel a hivatkozási forrásomnak elírási hibája van a -_- algoritmusban.

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

Néhány minta időzítéssel a “codereview” anagrammáinak megszámlálásához:

$ 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 

Megjegyzések

• Ez messze a győztes, kiszámítva a 3 628 800 eredmény a ~5,000ms!
• szépben! A tömbméretek előzetes kiszámításával valószínűleg még nagyobb eredményeket érhet el (mivel az anagrammák és a számláló hatalmas tömbök). Azt hiszem, megpróbálom elosztott megközelítést alkalmazni, hogy ezt legyőzzem 🙂
• Érdekes, hogy ez hogyan méretezhető a különböző méretű bemenetekkel iv. ‘ id = “ceaff87c8c”>

Amint jobb megoldást dolgoztam ki, kitaláltam, hogy az új JS Iterators & Generátorok , amelyekről olvastam. Ma valószínűleg 6 órát töltöttem ezen a megoldással, és ez volt percenként érdemes. Van néhány formázási hiba, de teljesen a teljesítményre fogok koncentrálni , és otthagyom a formázást a többi bírálónak.

---

Ha ezt nagy szóval futtatod, megsüti a gépedet

Rendben, szóval ez talán kicsit re is megy messze, de komolyan, ez egy drága függvény. I “nincs matematikai guru, tehát Ezt a kérdést a Math.SE webhelyen tettem fel. .

A lehetséges kombinációk számának képlete rendkívül meredek:

Gondoljon így:

Hány választása van az első betűre? Négy: 4_ _ _ _.

A másodikra? Három: 4⋅3 _ _.

Folytassa így, és összesen 4⋅3⋅2⋅1 = 4! = 24 választási lehetőséget talál. – MrRicci

A függvény futtatása a szó ellen Az “Enciklopédia” határozott oldalösszeomlást eredményez, ha ügyféloldali futtatja. Tehát ennek kijavítására elgondolkodtam.

---

Vigyél velem – Ez egyre fontosabbá válik, ahogy olvasol.

Meg akartam próbálni valódi szavak létrehozását (szórakozás a codezzel)

An Az anagramma egyfajta szójáték, amelynek eredményeként egy szó vagy kifejezés betűit átrendezzük új szó vagy kifejezés létrehozására, az összes eredeti betű pontosan egyszer használva – Wikipeda

Ha egy anagrammára gondolok, akkor az eredmény valódi szavakra vagy kifejezésekre gondolok. Noha a kód felülvizsgálatának célja nem a kód funkcionalitásának megváltoztatása, én nem tudtam segíteni, de szórakozni akarok rajta. Ezért úgy döntöttem, hogy keresek egy megoldást, amely lehetővé teszi számomra, hogy kiszűrjem és kinyomtassam az összes valódi szó anagrammát az eredményből.

Miután végre felkutattam egy ~ 130 000 angol szó t, hogy szavakként használjam, akkor ezt a listát JS-be kellett konvertálnom.Tehát egy olyan függvényt építettem, amely szeleteli a karakterláncot minden téren, és kinyomtatja a kulcsolt tulajdonságokkal rendelkező objektum felépítését, hogy a worldList["word"] -> returns true if word is valid.

130 000 szó listájának kinyomtatása a dokumentum törzsébe JSON karakterláncként, hasonlóan a funkciójához, nagyon drága.

---

… És a relevancia:

Tehát itt találkozik a problémája azzal a problémával, amelyet magam találtam ki. Hogyan dolgozza fel a nagyon drága hurok egy weboldal összeomlása nélkül?

A lehetőségekkel kísérletezve valóban felfedeztem egy módot, amellyel engedélyezhetem a funkcióm működését kezeljen 130 000 szót, és az Ön feladata, hogy fenntartson bármilyen méretű szót , a munkaterhelés időbeli kiegyensúlyozásával.

A hurkok néha túl gyorsak saját érdekében

A hurkok a lehető leggyorsabbak, ami a legtöbbre tökéletes azokból a feladatokból, amelyekhez a weboldalakon használjuk őket. De ha arra kérjük őket, hogy kezeljenek túl sokat, akkor a böngésző nem tudja kezelni.

Szükségem volt tehát egy olyan megoldásra, amely lehetővé tenné számomra a munkaterhelés időbeli elosztását annak érdekében, hogy az oldal kezelhesse drága ciklusok probléma nélkül.

Az én megoldásom egy kézi hurok létrehozása volt egy olyan függvényen keresztül, amely x alkalommal hívta magát, és beillesztett egy 1-2ms késleltetés az iterációk között. Ez elegendő időt adott az oldalnak a hurok kezelésére, amely késedelem nélkül feldolgozta a szavakat őrülten gyorsan a C-ig, mielőtt összeomlik. Ez nagyszerűen működött a JSON szavak felépítésének létrehozásakor.

De a késleltetett ciklus rendkívül bonyolult volt a már rekurzív függvényben megvalósítani.

Akkor jöttem rá, hogy ez a tökéletes helyzet egy olyan megoldás alkalmazásához, amelyet a közelmúltban olvastam a JavaScript-hez …

---

JavaScript Iterátorok és Generátorok

Tehát, itt jönnek a JavaScript Iterátorok & Generátorok a megmentéshez.

Ez az áttekintés már azt a kockázatot jelent, hogy szörnyeteggé válhat, ezért a Generátorok magyarázata helyett idézni fogom ezt a hamarosan népszerű választ “s egyvonalas:

TL; DR: a [egy] generátor használatának lényege a kódfuttatás felfüggesztésének szabályozása.

És magyarázza el egyszerűen, hogy a generátorok jobb módon hajtják végre az iterátorokat.

A többit magának olvashatja el az ottani válaszban. Ha ez a válasz nem elég az Ön számára, akkor a következő forrásokkal javíthatja megértését:

• Javascript “s Jövő: Generátorok

• Generátorok: jobb módszer az itterátorok felépítésére

• Generátorok – MDN

• Hogy hívják ezt a dolgot generátoroknak?

Most a generátoroknak nagy lehetőségeik vannak a visszahívási pokol elkerülése terén, de mi itt ne a & struktúra formázására használja őket, hanem a teljesítményre, ami (teljesítményem szerint elfogult véleményem szerint) a legelegánsabb ok használatukra.

Még nem vagyok biztos benne, hogy a generátorok a legjobb megoldást jelentik-e itt, de a legjobb ötletem van, és ez ürügy ezek kipróbálására.

---

A kód generátorokkal

ez a megoldás még mindig. Remekül kellene működnie, még nincs időm befejezni, és előbb-utóbb szerettem volna felajánlani a továbbfejlesztett kódot. Hamarosan közzéteszem ezt a megoldást.

Frissítés: Néhány nap később még nem fejeztem be a generátorok tanulását, egészen addig a pontig, hogy ezt a függvényt helyesen megírhassam velük. Feltétlenül felteszem ide, amint a szintaxisukat kicsit jobban kitalálom.

---

És végül, mivel a generátorok újak és még nem támogatott mindenhol .. A kód javított változata nélkülük

Megjegyzés: A formázási gyakorlataim általában a saját olvashatóságom preferencia, nem pedig a legjobb gyakorlat. Ne érezze kötelességét, hogy a kódot így formázza.

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

A változók ciklusokon kívüli deklarálásával jelentősen spórolunk, mivel látni fogod az eredményekben. Továbbá úgy vélem, hogy word.slice() valamivel jobban teljesített, mint a word.substr(). Ezen optimalizálások között ez a kód fellép tter, mint az eredeti kódod.

---

És utoljára, de nem utolsósorban, a teljesítmény eredménye!

Eredeti kód : Az eredmények frissítve! Az oldal nem ütközik naplózás nélkül.

• “kód”, 4 karakter: 24 találat , ~ 1ms
• “kódoló”, 5 karakter: 120 találat , ~ 1ms
• “kódoló”, 6 karakter: 720 találat , ~ 6ms
• “coderev”, 7 karakter: 5040 találat , ~ 11ms
• “coderevi”, 8 karakter: 40.320 találat , ~ 75ms
• “coderevie”, 9 karakter: 362.880 találat , az oldal sikertelen
• “codereview”, 10 karakter: 3 628 800 eredmény , az oldal nem működik

Továbbfejlesztett kód : Frissítve az eredmények – Az oldal naplózás nélkül összeomlik.

• ” kód “, 4 karakter: 24 találat , ~ 0.5ms
• ” kódoló “, 5 karakter: 120 találat , ~ 0,5 ms
• “kódere”, 6 karakter: 720 találat , ~ 1,5 ms
• “coderev”, 7 karakter: 5040 találat , ~ 8ms
• ” coderevi “, 8 karakter: 40 320 eredmény , ~ 53ms
• ” coderevie “, 9 karakter: 362 880 találat , ~ 556ms
• “codereview”, 10 karakter: 3 628 800 eredmény , ~ 12725ms

Valós idejű generátorokkal

(A kód nem teljes – a generátorok kissé nehéznek bizonyulnak)

console.time() a milliszekundum pontossággal pontos mérések eléréséhez, mindegyik 3-5 kísérletet kitöltve, és becsülve az általános átlagot az r esults. Ezek az eredmények természetesen gépenként változnak. Az idő összehasonlítások a kulcsok a referenciaértékek olvasásához, nem pedig a sebességek.

---

Tl; Dr. összefoglaló, ahogy ígértük

A hurkok rendkívül hatékonyak eszköz a programozásban, de nem kezelik jól a szörnyeteg drága iterációt a webböngészőben. Az ehhez hasonló drága looping funkciók tökéletesen teljesítenek, ha azonban a munkaterhelést idővel elosztja. Ennek egyik érdekes módja a JS Generators használata , egy új játék, amely ma elérhető a webáruházakban, de nem feltétlenül a helyi piacokon, ezért körültekintően használja, amíg a JS 2.0 szélesebb körűen megvalósul! A JS generátorok erejének kihasználásával kezelhetjük a régóta futó drága folyamatokat anélkül, hogy bármilyen teljesítményproblémát látnánk.

Megjegyzések

• valaha is kitaláltad a generátorokat?
• @megawac sok órát töltöttem rajta, annyi útmutató / információ / oktatóanyag nélkül, hogy valóban rájöjjek, hogyan kell csinálni. I ‘ költöttem annyi időm van, mint amennyi napom van a bejegyzés óta, hogy tanulmányozhassam őket, de … Nem ‘ nem tanulok gyorsan a nyers dokumentációból. Tudsz valami jó erőforrást a generátorokról és az iterátorokról?
• Jó stackoverflow szálnak hangzik @ jt0dd
• írtam megoldót a helyi lapnak ‘ s zűrzavar. Volt egy listám, amelyen 600 000 összekeverhető szó található, és amelyeket előre feldolgoztam az egyes szavak betűinek rendezéséhez. Ezután ugyanezt tettem a kereső betűkkel és megpróbáltam szavakat találni. Ez minden, 10 és 10 betű közötti szót képes beolvasni, 10 betű milliszekundumban. A ‘ throb ‘ betűk bármilyen sorrendben megadva ‘ bhort ‘ amely közvetlenül kapcsolódik a ‘ lüktetéshez ‘ és ‘ húsleves ‘, nem kell minden kombinációt kipróbálni. Például, ha 4 betűs szót keresünk, 5 betű van, akkor csak 4 kombináció van a betűk rendezésénél, ha nem, akkor 120.
• @ jt0dd I ‘ m zavaros a szelet használatakor a word.length + 1 szó használatáról. Meg tudná magyarázni?

Megnéztem a @ jt0dd kódot, és kíváncsi voltam, hogyan tudna még néhány esetet kezelni. Megmondom, beengedem a gyorsítótárréteget, és előre kiszámolom a kapott tömbök hosszát!

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

Ez az ember ” csúnya! Remélem, hogy ez az idő semmiért nem volt semmi …

Előre kiszámított kivonatok

• “kód”, 4 karakterek: 24 találat , < = 1ms
• “kódoló”, 5 karakter: 120 találat , < = 1ms
• “codere”, 6 karakter: 720 találat , < = 1ms
• “coderev”, 7 karakter: 5040 találat , < = 3ms
• ” coderevi “, 8 karakter: 40 320 eredmény , < = 18ms
• “coderevie”, 9 karakter: 362 880 eredmény , 135 ms
• “codereview”, 10 karakter: 3 628 800 eredmény , 2,1 s

Hoppá, teljesítettük a kihívást. Lássuk, “mennyivel tovább mehetünk. codereview csak egy kemény szó duplikát e karakter. Próbálkozzunk valami könnyebbel a következőnél menjünk. Próbálja ki a "anagramarmy"

… … …

Rendben, többet haraptam le, mint amennyit a böngészőm képes rágni úgy tűnik, 40 millió string-permutáció túllépi a határt 🙁

Megfigyeli, hogy a verem túlcsordulásának elkerülése érdekében átterveztem az algoritmust – a rekurzión kívül kell keresni.

Növelhetjük algoritmusunk összeomlásának esélyét azáltal, hogy aszinkronvá tesszük, és minden mondanivalót 100,000 minden milliszekundumban elvégezünk, hogy elkerüljük a leállást.

Megjegyzések

• Félelmetes! Ez sokkal jobb, mint az I ‘ m generátor verziója. +1 ( Ezt a választ el kell fogadni, ez ‘ sokkal hatékonyabb lesz, mint az én generátoros megoldásom.)
• Zseniális … Csak zseniális. Nagyon mint ez. Amikor befejezem a valós idejű harmóniagenerátor megoldást (vagy megvalósíthatja a sajátját), nyugodtan vegye ezt és tegye ugyanezt vele. ‘ lassabb lesz, de a valós idejű eredményt eredményezi, és nincs vége annak, hogy mekkora szót képes kezelni.
• ahh, mjolka megvert minket mind a far által.
• Szia, hogyan tudom végrehajtani ezt a kódot a tartományomon belüli html és css mellett?

Két szkriptet készítettem:

1. Az első gyors, de “nem képes sokat tartani;
2. A második lassú, de korlátlan eredményt tud felmutatni.

Mindkettő az általam készített prototípust használja: fastPush, fastSplit és fastJoin; amelyek gyorsabbak, mint a szokásos módszer, osztódnak és csatlakoznak. Mindkettő szintén használd bitenként, hogy ellenőrizd-e, hogy páros vagy páratlan, mert tudom, hogy a mod a lehető leglassabb művelet a számítógépen.

Az első szkript mások gyorsabb eredményét több mint 750 ms-mal (átlagosan) megveri a 10 karakteres permutációs kihíváson .

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

Mindenesetre ennek az első programnak van egy korlátja, és felszakítja az oldalt, ha 10-nél több karaktert próbál ki.

A második program (a az egyik lent) önhívó funkciót használ, és bejelentkezik a 4e4 elem konzoldarabjaiba, minden alkalommal kitörli az anagrammák tömbjét, amikor egy darabot ad ki, és törli a nsole.log 5 darabot (elég ahhoz, hogy láthassa ezeket a kombinációkat). A függvény önhívásához a setZeroTimeout ( David Baron blogja ) a setTimeout helyett használja, mert a setTimeout sokkal lassabb.

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

Még egy változat (i C írva) egyszerű számlálóval az Az összes karaktersorozat beállítása .

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

Futtatás az összes húr nyomtatásával:

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

Megjegyzések

• Mit értesz az összes karakterlánc ” nyomtatásánál “? A függvényed csak a szó egy részét adja ki, pl. ha a run` anagrams abc kimeneti a,b,ab,c,ac,bc,abc

Gépelt tömbök a jobb teljesítmény érdekében.

Az elfogadott válaszok módszerével megduplázza a teljesítményt.

A nyerő válasz futtatása a gépemen összehasonlító értéket adott

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

És amikor t yped tömbök

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

a 3,68-as teljesítménynövekedéshez.

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

Még egy kicsit élesíteni előre definiálhatja az eredménytömböt, hogy megszerezhesse

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

Ha akár 3,95-szer gyorsabban javítaná, mint a nyertes válasz.