단어에서 가능한 모든 문자 조합 생성

순열을 생성하는 반복적 인 버전의 힙의 방법 을 사용하여 내 모자를 던질 것입니다. 내 참조 소스 에 알고리즘 -_-에 오타가 있으므로 제대로하는 데 시간이 걸렸습니다.

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

“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 

댓글

• 이것은 를 계산하여 우승자 멀리 입니다. > 3,628,800 개의 결과 ~ 5,000ms!
• 좋아요! 배열 크기를 미리 계산하면 훨씬 더 큰 결과를 얻을 수 있습니다 (애너그램과 카운터는 방대한 배열이므로). 나는 이것을 이기기 위해 분산 접근 방식을 취해야 할 것이라고 생각합니다 🙂
• ‘ 이것이 다른 크기 입력으로 어떻게 확장되는지 흥미 롭습니다. jsperf.com/getanagramsc-r/2
• @megawac이 접근법의 강점을 활용 한 후 귀하의 접근법을보고 싶습니다.

더 나은 솔루션을 연구하면서 새로운 JS Iterators & Generators 에 대해 읽어 봤습니다. 오늘은이 솔루션을 다루며 6 시간을 보냈을 것입니다. 일부 형식 오류가 있지만 성능에 전적으로 집중하고 형식은 그대로 두겠습니다. 다른 리뷰어에게 전달합니다.

큰 단어에 대해이 작업을 실행하면 컴퓨터가 튀어 나올 것입니다.

좋아요. 그래서 그게 작게 될 수도 있습니다. 멀지 만 진지하게, 이것은 값 비싼 함수입니다. 저는 수학 전문가가 아니므로 Math.SE에서이 질문을했습니다 .

가능한 조합 수를 계산하는 공식은 매우 가파 릅니다.

다음과 같이 생각해보십시오.

첫 글자에 대해 얼마나 많은 선택지가 있습니까? 4 : 4_ _ _ _.

두 번째? 셋 : 4⋅3 _ _.

이렇게 계속하면 총 4⋅3⋅2⋅1 = 4! = 24 개의 선택 항목이 있음을 알 수 있습니다. -MrRicci

단어에 대해 함수 실행 “백과 사전”은 클라이언트 측에서 실행하는 경우 명확한 페이지 충돌이 발생합니다. 이 문제를 해결하기 위해 몇 가지 생각을했습니다.

참여하세요. 읽을수록 관련성이 높아집니다.

실제 단어를 생성 해보고 싶었습니다 (codez로 재미있게 즐기기)

An anagram은 단어 놀이의 한 유형으로, 모든 원래 문자를 정확히 한 번 사용하여 새로운 단어 또는 구문을 생성하기 위해 단어 또는 구문의 문자를 재배 열한 결과입니다-Wikipeda

애너그램을 생각하면 그 결과가 진짜 단어 나 구문이라고 생각합니다. 이제이 코드 검토의 목적은 “코드의 기능을 변경하는 것이 아니지만”나는 도움을 줄 수는 없지만 재미있게 만들고 싶습니다. 그래서 결과에서 실제 단어 애너그램을 필터링하고 인쇄 할 수있는 솔루션을 찾기로 결정했습니다.

드디어 ~ 130,000 영어 단어 를 내 단어 목록으로 사용하기 위해이 목록을 JS로 변환해야했습니다.그래서 각 공간에서 문자열을 슬라이스하고 키가있는 속성이있는 객체의 구조를 인쇄하는 함수를 만들었습니다. 그래서 worldList["word"] -> returns true if word is valid.

문서 본문에 130,000 개의 단어 목록을 JSON 문자열로 인쇄하는 것은 함수와 마찬가지로 매우 비쌉니다.

… 그리고 관련성 :

여기에서 제가 스스로 발명 한 문제와 만나는 문제가 있습니다. 어떻게 웹 페이지를 중단하지 않고 비용이 많이 듭니까?

가능성을 실험하면서 실제로 내 함수를 허용하는 방법을 발견했습니다. 시간이 지남에 따라 작업 부하의 균형을 조정하여 130,000 단어 및 모든 크기의 단어를 유지하는 기능 을 처리합니다.

루프가 때때로 너무 빠릅니다. 자신의 이익을 위해

루프는 최대한 빠른 속도로 만들어져 대부분의 웹 페이지에서 사용하는 작업의 하지만 너무 많이 처리하도록 요청하면 브라우저에서 처리 할 수 없습니다.

그래서 페이지가 처리 할 수 있도록 시간이 지남에 따라 작업 부하를 분산시킬 수있는 솔루션이 필요했습니다. 문제없이 비용이 많이 드는 루프입니다.

내 솔루션은 자신을 x 번 호출하는 함수를 통해 수동 루프를 구축하고 1-2ms 반복 사이의 지연. 이로 인해 페이지에서 루프를 처리 할 수있는 충분한 시간이 주어졌습니다 . 지연없이 단어를 처리했습니다. 매번 충돌하기 전에 C “가 될 때까지 미친 듯이 빠르게. 이것은 내 JSON 단어 목록 구조를 생성하는 데 효과적이었습니다.

그러나 지연된 루프는 이미 재귀 함수에서 구현하기가 매우 까다로 웠습니다.

그때 저는 이것이 최근에 JavaScript에 대해 읽은 솔루션을 활용하기에 완벽한 상황이라는 것을 깨달았습니다 …

JavaScript 반복기 및 생성기

그러므로 여기에 JavaScript 반복기 & 생성기가 있습니다.

@ jt0dd “의 코드를 살펴보고 우리가 어떻게 더 많은 경우를 처리 할 수 있습니다. 캐시 레이어를 추가하고 결과 배열의 길이를 미리 계산해 보겠습니다.

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 ” 정말 못 생겼어! 그 모든 시간이 쓸데없는 게 아니 었으면 좋겠어 …

사전 계산 된 해시

• “code”, 4 문자 : 24 개의 결과 , < = 1ms
• “coder”, 5 자 : 120 개의 결과 , < = 1ms
• “codere”, 6 자 : 720 개의 결과 , < = 1ms
• “coderev”, 7 자 : 5040 개의 결과 , < = 3ms
• “coderevi “, 8 자 : 40,320 개 결과 , < = 18ms
• “coderevie”, 9 자 : 362,880 개 결과 , 135ms
• “codereview”, 10 자 : 3,628,800 개의 결과 , 2.1 초

우와, 우리는 도전을 만났습니다. 우리가 얼마나 더 나아갈 수 있는지 봅시다. codereview는 어려운 단어로 e 문자 만 중복됩니다. 다음에 더 쉬운 것을 시도해 보겠습니다. 가자. "anagramarmy"

… … …

좋아, 브라우저가 씹을 수있는 것보다 더 많이 4 천만 개의 문자열 순열이 한계를 벗어난 것 같습니다. (

스택 오버플로를 방지하기 위해 알고리즘을 재 설계했음을 알 수 있습니다. 조회는 재귀 밖에서 수행해야합니다.

알고리즘을 비동기로 만들고 밀리 초마다 모든 say 100,000 요소를 수행하여 중단을 방지함으로써 알고리즘이 충돌하지 않을 가능성을 높일 수 있습니다.

댓글 h3>

• 굉장합니다. 작업중인 생성기 버전 ‘보다 훨씬 낫습니다. +1 ( 이 대답은 받아 들여 져야합니다. ‘ 제 생성기 솔루션보다 훨씬 더 효율적입니다.)
• 훌륭합니다 … 아주 훌륭합니다. 이렇게. 실시간 하모니 제너레이터 솔루션을 완료하면 (또는 직접 구현할 수 있습니다) 자유롭게 가져 와서 똑같이하십시오. ‘ 느려지지만 실시간으로 결과를 반환하고 처리 할 수있는 단어의 크기에 끝이 없습니다.
• 아, mjolka가 우리를 이겼습니다. 둘 다 멀리 입니다.
• 안녕하세요,이 코드를 도메인 내에서 사이드 html 및 css와 함께 어떻게 실행합니까? ‘이 무료 서비스를 사용하고 있습니다 : morsetovoynich.000webhostapp.com

두 개의 스크립트를 만들었습니다.

1. 첫 번째 스크립트는 빠르지 만 많이 담을 수는 없습니다.
2. 두 번째는 느리지 만 무제한의 결과를 표시 할 수 있습니다.

둘 다 내가 만든 프로토 타입 인 fastPush, fastSplit 및 fastJoin을 사용합니다. 이는 표준 분할 및 결합 방법보다 빠릅니다. 나는 mod가 컴퓨터에서 가능한 가장 느린 작업이라는 것을 알고 있기 때문에 bitwise를 사용하여 홀수인지 짝수인지 확인합니다.

첫 번째 스크립트는 10 문자 순열 도전에서 다른 스크립트보다 가장 빠른 결과를 750ms 이상 (평균) 이깁니다. .

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

어쨌든이 첫 번째 프로그램에는 제한이 있으며 10 자 이상 시도하면 페이지가 중단됩니다.

두 번째 프로그램 ( 아래 하나) 자체 호출 함수를 사용하고 4e4 요소의 콘솔 청크에 로그인하면 청크를 출력 할 때마다 anagrams 배열을 지우고 co nsole.log 각 5 개의 청크 (이러한 조합을 볼 수있을만큼 충분 함). 함수를 자체 호출하기 위해 프로그램은 setTimeout이 훨씬 느리기 때문에 setTimeout 대신 setZeroTimeout ( David Baron의 블로그 )을 사용합니다.

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

파워 세트 .

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

모든 문자열 인쇄로 실행 :

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

댓글

• ” 모든 문자열 인쇄의 의미 “? 함수는 단어의 일부만 출력합니다. 예를 들어 run` anagrams abc` 출력 a,b,ab,c,ac,bc,abc

성능 향상을위한 유형 배열

허용되는 답변 방법을 사용하면 성능을 3 배로 높일 수 있습니다.

내 컴퓨터에서 우승 한 답변을 실행하면 벤치마킹되었습니다.

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

그리고 t를 사용할 때 yped 배열

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

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

조금 더 결과 배열을 미리 정의하여

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

이기는 답변보다 최대 3.95 배 빠르게 개선 할 수 있습니다.