Generuj wszystkie możliwe kombinacje liter w słowie

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

Zamierzam rzucić swój kapelusz na ring z iteracyjną wersją metody stosu generowania permutacji. Zajęło mi to trochę czasu, ponieważ moje źródło odniesienia zawiera literówkę w algorytmie -_-.

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

Z pewnymi przykładowymi czasami liczenia anagramów „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 

Komentarze

• To jest zdecydowanie daleko zwycięzca, obliczając 3 628 800 wyników w czasie ~5 000ms!
• Świetnie! Powinieneś wstępnie obliczyć rozmiary tablic, które prawdopodobnie dadzą jeszcze lepsze wyniki (ponieważ anagramy i licznik to masywne tablice). Myślę, że spróbuję zastosować podejście rozproszone, aby pokonać ten problem 🙂
• To ' jest interesujące, jak to skaluje się z różnymi danymi wejściowymi jsperf.com/getanagramsc-r/2
• @megawac Chciałbym zobaczyć Twoje podejście po wykorzystaniu mocnych stron tego podejścia.

Pracując nad lepszym rozwiązaniem, odkryłem świetne zastosowanie nowego Iteratory JS & Generatory , o których czytałem. Spędziłem dziś prawdopodobnie 6 godzin bawiąc się tym rozwiązaniem. warte każdej minuty. Wystąpiły błędy formatowania, ale Skupię się całkowicie na wydajności i zostawię formatowanie innym recenzentom.

---

Uruchomienie tego z wielkim słowem usmaży Twoją maszynę

Ok, więc może to też będzie trochę daleko, ale poważnie, to droga funkcja. Nie jestem mistrzem matematyki, więc Zadałem to pytanie na Math.SE .

Wzór na obliczenie liczby możliwych kombinacji jest niezwykle stromy:

Pomyśl o tym w ten sposób:

Ile masz możliwości wyboru pierwszej litery? Cztery: 4_ _ _ _.

Po drugie? Trzy: 4⋅3 _ _.

Kontynuuj w ten sposób, a zobaczysz, że są 4⋅3⋅2⋅1 = 4! = Łącznie 24 możliwości. – MrRicci

Uruchamianie funkcji w stosunku do słowa „Encyklopedia” spowoduje definitywną awarię strony, jeśli uruchomisz ją po stronie klienta. Aby to naprawić, trochę się zastanawiałem.

---

Trzymaj się ze mną – to staje się coraz bardziej istotne w miarę czytania.

Chciałem spróbować wygenerować prawdziwe słowa (dobrze się bawić przy kodowaniu)

An anagram to rodzaj gry słów, będący wynikiem zmiany kolejności liter słowa lub frazy w celu utworzenia nowego słowa lub frazy, przy użyciu wszystkich oryginalnych liter dokładnie raz – Wikipedia

Kiedy myślę o anagramie, myślę o wyniku jako prawdziwych słowach lub frazach. Teraz, chociaż celem tego przeglądu kodu nie jest zmiana funkcjonalności twojego kodu, nie mogłem pomóc, ale chciałem się trochę bawić. Postanowiłem więc poszukać rozwiązania, które pozwoliłoby mi odfiltrować i wydrukować wszelkie prawdziwe anagramy słów z wyniku.

Kiedy w końcu wyśledziłem zwykły ciąg tekstowy ~ 130 000 angielskich słów do użycia jako mojej listy słów, musiałem następnie przekonwertować tę listę na JS.Zbudowałem więc funkcję do wycinania ciągu w każdej spacji i drukowania struktury obiektu z właściwościami z kluczem, dzięki czemu mogłem bardzo szybko sprawdzić poprawność dowolnego słowa za pomocą worldList["word"] -> returns true if word is valid.

Wydrukowanie listy 130 000 słów do treści dokumentu jako łańcucha JSON jest, podobnie jak funkcja, bardzo kosztowne.

---

… I trafność:

Oto, gdzie Twój problem spotyka się z tym, który sam sobie wymyśliłem. Jak radzisz sobie z bardzo kosztowna pętla bez awarii strony internetowej?

Podczas eksperymentowania z możliwościami odkryłem sposób, aby pozwolić mojej funkcji obsłuż 130 000 słów i swoją funkcję, aby utrzymać słowo dowolnej wielkości , równoważąc obciążenie pracą w czasie.

Pętle są czasami zbyt szybkie dla własnego dobra

Pętle są tak szybkie, jak to tylko możliwe, co jest idealne dla większości zadań, do których używamy ich na stronach internetowych. Ale jeśli poprosimy ich, aby obsłużyli zbyt wiele, przeglądarka sobie z tym nie poradzi.

Dlatego potrzebowałem rozwiązania, które pozwoliłoby mi rozłożyć obciążenie pracą w czasie, aby strona mogła obsłużyć drogie pętle bez problemu.

Moim rozwiązaniem było zbudowanie ręcznej pętli za pomocą funkcji, która nazywała siebie x razy, wstawiając 1-2 ms opóźnienie między iteracjami. Dało to stronie wystarczająco dużo czasu na obsłużenie pętli , która bez opóźnienia przetwarzała słowa szalenie szybko, aż do „C” przed awarią za każdym razem. To świetnie zadziałało przy generowaniu mojej struktury listy słów JSON.

Jednak opóźniona pętla była niezwykle trudna do zaimplementowania w już rekurencyjnej funkcji.

Zdałem sobie wtedy sprawę, że jest to idealna sytuacja do wykorzystania rozwiązania, o którym ostatnio czytałem dla JavaScript …

---

Iteratory i generatory JavaScript

A więc oto Iteratory JavaScript & Generatory na ratunek.

Ta recenzja już teraz może stać się potworem, więc zamiast wyjaśniać Generatory, zacytuję , która wkrótce stanie się popularna „s one-linier:

TL; DR: istotą [używania] generatora jest kontrolowanie zawieszenia wykonywania kodu.

I wyjaśnij po prostu, że generatory są w ulepszonym sposobie implementowania iteratorów.

Resztę możesz przeczytać samodzielnie w odpowiedzi. Jeśli ta odpowiedź nie wystarczy, możesz poprawić swoje zrozumienie, korzystając z następujących zasobów:

• Javascript „s Przyszłość: Generatory

• Generatory: lepszy sposób na tworzenie iteratorów

• Generatory – MDN

• Jak to się nazywa generatory?

Generatory mają duży potencjał, jeśli chodzi o unikanie piekła oddzwonienia, ale zamierzamy używać ich tutaj nie do formatowania struktury &, ale do wydajności, która jest (moim zdaniem zorientowana na wydajność) najbardziej eleganckim powodem ich używania.

Nie wiem jeszcze, czy generatory są tutaj najlepszym rozwiązaniem, ale to najlepszy pomysł, jaki mam, a to to wymówka, aby je wypróbować.

---

Twój kod z generatorami

Praca nad to rozwiązanie nadal. Powinno działać dobrze, po prostu nie mam jeszcze czasu na zakończenie i chciałem zaoferować ulepszony kod wcześniej niż później. Wkrótce opublikuję to rozwiązanie.

Aktualizacja: kilka dni później nie skończyłem uczyć się generatorów, do tego stopnia, że nie mogłem poprawnie napisać z nimi tej funkcji. Na pewno opublikuję to tutaj, gdy tylko trochę lepiej zrozumiem ich składnię.

---

I wreszcie, ponieważ generatory są nowe i nie wszędzie są jeszcze obsługiwane .. Ulepszona wersja twojego kodu bez nich

Uwaga: moje praktyki formatowania są generalnie moją własną czytelnością zamiast najlepszych praktyk. Nie czuj się zobligowany do formatowania kodu w ten sposób.

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

Deklarując zmienne poza pętlami, oszczędzamy znacznie, ponieważ zobaczysz w wynikach. Uważam też, że word.slice() działał nieco lepiej niż word.substr(). Pomiędzy tymi dwiema optymalizacjami ten kod wykonuje be tter niż oryginalny kod.

---

I na koniec, wyniki wydajności!

Oryginalny kod : Zaktualizowano wyniki! Strona nie ulega awarii bez logowania.

• „kod”, 4 znaki: 24 wyniki , ~ 1 ms
• „koder”, 5 znaków: 120 wyników , ~ 1 ms
• „codere”, 6 znaków: 720 wyników , ~ 6 ms
• „coderev”, 7 znaków: 5040 wyników , ~ 11 ms
• „coderevi”, 8 znaków: 40 320 wyników , ~ 75ms
• „coderevie”, 9 znaków: 362 880 wyników , błąd strony
• „codereview”, 10 znaków: 3 628 800 wyników , błąd strony

Ulepszony kod : Zaktualizowano wyniki – Strona nie” nie ulega awarii bez logowania.

• „kod”, 4 znaki: 24 wyniki , ~ 0,5 ms
• ” koder „, 5 znaków: 120 wyników , ~ 0,5 ms
• „codere”, 6 znaków: 720 wyników , ~ 1,5 ms
• „coderev”, 7 znaków: 5040 wyników , ~ 8ms
• ” coderevi „, 8 znaków: 40 320 wyników , ~ 53ms
• ” coderevie „, 9 znaków: 362 880 wyników , ~ 556ms
• „codereview”, 10 znaków: 3 628 800 wyników , ~ 12725ms

W czasie rzeczywistym z generatorami

(Kod niekompletny – generatory okazują się nieco trudne)

Użyłem console.time(), aby uzyskać pomiary z dokładnością do najbliższej milisekundy, wykonując 3-5 prób każda i szacując ogólną średnią na podstawie r wyniki. Wyniki te będą oczywiście różnić się w zależności od maszyny. Porównania czasowe są kluczem do czytania testów porównawczych, a nie szybkości.

---

Podsumowanie Tl; Dr, zgodnie z obietnicą

Pętle są niezwykle potężne narzędzie w programowaniu, ale nie radzą sobie dobrze z ogromną liczbą drogich iteracji w przeglądarce internetowej. Drogie funkcje zapętlania, takie jak ta, działają doskonale, jednak jeśli rozłożymy obciążenie w czasie. Ciekawym sposobem na to jest użycie generatorów JS , nowa zabawka dostępna obecnie w sklepach internetowych, ale niekoniecznie na rynkach lokalnych, więc używaj jej ostrożnie, dopóki JS 2.0 nie zostanie szerzej wdrożona! Wykorzystując moc generatorów JS, możemy zarządzać długotrwałymi i kosztownymi procesami bez żadnych problemów z wydajnością.

Komentarze

• Zrobione zdarzyło Ci się odkryć generatory?
• @megawac Spędziłem nad nim wiele godzin bez wystarczającej liczby przewodników / informacji / samouczków, aby naprawdę dowiedzieć się, jak to zrobić. ' Wydawałem tyle czasu, ile mam wolnego każdego dnia od tego postu, aby je przestudiować, ale … Nie ' nie uczę się szybko z surowej dokumentacji. Czy znasz jakieś dobre zasoby na temat generatorów i iteratorów?
• Brzmi jak dobry wątek przepełnienia stosu @ jt0dd
• Napisałem solver dla lokalnej gazety ' s Jumble puzzle. Miałem listę 600 000 słów do scrabble, które wstępnie przetworzyłem, aby posortować litery w każdym słowie. Następnie zrobiłem to samo dla wyszukiwanych liter i spróbowałem znaleźć słowa. Może skanować wszystkie słowa od 4 do 10 liter, które mają 10 liter w milisekundach. Litery ' throb ' wprowadzone w dowolnej kolejności skutkują ' bhort , który prowadzi bezpośrednio do ' throb ' i ' bulion ', nie trzeba próbować każdej kombinacji. Na przykład, jeśli szukasz 4-literowych słów zawierających 5 liter, to są tylko 4 kombinacje, kiedy litery są posortowane, 120 jeśli nie.
• @ jt0dd I ' m zdezorientowany o używaniu word.length + 1 podczas korzystania z slice. Czy możesz wyjaśnić?

Rzuciłem okiem na kod @ jt0dd „i zastanawiałem się, jak możemy mógłby obsłużyć więcej przypadków. Powiem ci, dodajmy warstwę pamięci podręcznej i obliczmy wstępnie długości wynikowych tablic!

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

Człowieku, że ” brzydki! Mam nadzieję, że cały ten czas nie poszedł na marne …

Wstępnie obliczone hashy

• „kod”, 4 znaki: 24 wyniki , < = 1 ms
• „coder”, 5 znaków: 120 wyników , < = 1 ms
• „codere”, 6 znaków: 720 wyników , < = 1 ms
• „coderev”, 7 znaków: 5040 wyników , < = 3ms
• ” coderevi „, 8 znaków: 40 320 wyników , < = 18 ms
• „coderevie”, 9 znaków: 362 880 wyników , 135ms
• „codereview”, 10 znaków: 3628800 wyników , 2,1 s

Whoopy, sprostaliśmy wyzwaniu. Zobaczmy, jak daleko możemy się posunąć. codereview to trudne słowo, tylko zduplikowane e znaki. Spróbujmy czegoś łatwiejszego na następny idź. Spróbujmy "anagramarmy"

… … …

OK, przegryzłem więcej, niż moja przeglądarka jest w stanie przeżuć Wygląda na to, że 40 milionów permutacji ciągów wydaje się przekraczać limit 🙁

Zauważysz, że przeprojektowałem algorytm, aby uniknąć przepełnienia stosu – wyszukiwania powinny być wykonywane poza rekurencją.

Możemy zwiększyć prawdopodobieństwo, że nasz algorytm nie ulegnie awarii, ustawiając go asynchronicznie i wykonując każde słowo 100,000 elementy co milisekundę, aby uniknąć zatrzymania.

Komentarze

• Super! To jest dużo lepsze niż wersja generatora, nad którą pracuję '. +1 ( Ta odpowiedź powinna zostać zaakceptowana, to ' będzie zdecydowanie bardziej wydajne niż moje rozwiązanie generatora.)
• Świetnie … Po prostu genialnie. Naprawdę lubię to. Kiedy skończę pracę nad generatorem harmonii w czasie rzeczywistym (lub możesz wdrożyć własne), nie krępuj się i zrób to samo. To ' będzie wolniejsze, ale zwróci wyniki w czasie rzeczywistym i nie będzie miało końca, jak duże słowo może obsłużyć.
• ahh, mjolka nas pokonał zarówno dalekie .
• Cześć, jak mam wykonać ten kod obok html i css w mojej domenie? Korzystam ' z tego bezpłatnego: morsetovoynich.000webhostapp.com

Zrobiłem dwa skrypty:

1. Pierwszy jest szybki, ale nie może wiele pomieścić;
2. Druga jest powolna, ale może dać nieograniczone wyniki.

Oba używają prototypów, które stworzyłem: fastPush, fastSplit i fastJoin; które są szybsze niż standardowa metoda split and join. użyj bitowego, aby sprawdzić, czy jest nieparzysty czy parzysty, ponieważ wiem, że mod jest najwolniejszą operacją możliwą na komputerze.

Pierwszy skrypt bije najszybszy wynik innych o ponad 750 ms (średnio) na 10-znakowym wyzwaniu permutacji .

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

W każdym razie ten pierwszy program ma ograniczenie i zepsuje stronę, jeśli spróbujesz więcej niż 10 znaków.

Drugi program ( jeden poniżej) używa funkcji samoczynnego wywoływania i loguje się do fragmentów konsoli elementów 4e4, czyści tablicę anagramów za każdym razem, gdy wyprowadza fragment, a także czyści co nsole.log co 5 fragmentów (wystarczy, abyś mógł zobaczyć te kombinacje). Aby samodzielnie wywołać funkcję, program używa setZeroTimeout ( blog Davida Barona ) zamiast setTimeout, ponieważ setTimeout jest znacznie wolniejszy.

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

Jeszcze inny wariant (napisany w C) wykorzystujący prosty licznik na Power Set wszystkich ciągów.

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

Uruchom z wypisywaniem wszystkich ciągów:

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

Komentarze

• Co masz na myśli przez ” wydruk wszystkich ciągów „? Twoja funkcja wyświetla tylko części słowa, np. if run` anagrams abc` wyświetla a,b,ab,c,ac,bc,abc

Tablice wpisane dla lepszej wydajności.

Za pomocą metody akceptowanych odpowiedzi można potroić wydajność.

Uruchomienie zwycięskiej odpowiedzi na moim komputerze dało test porównawczy

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

A gdy używasz t tablice yped

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

w celu zwiększenia wydajności 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; } 

Jeszcze trochę możesz wstępnie zdefiniować tablicę wyników, aby uzyskać

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

Aby poprawić ją nawet 3,95 razy szybciej niż zwycięska odpowiedź.