単語内の文字の可能なすべての組み合わせを生成する

順列を生成するヒープの方法の反復バージョンを使用して帽子をリングに投げ込みます。 参照ソースのアルゴリズムにタイプミスがあるため、正しく理解するのに少し時間がかかりました-_-。

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イテレータ&ジェネレータについて読んでいます。今日はおそらく6時間かけてこのソリューションをいじっていましたが、 1分ごとの価値があります。フォーマットエラーが発生しましたが、パフォーマンスに完全に集中します

これを大きな単語に対して実行すると、マシンが炸裂します

わかりました。それで、少しもうまくいくかもしれません。はるかに、しかし真剣に、 これは高価な関数です。 私は数学の第一人者ではないので、 Math.SEでこの質問をしました。

可能な組み合わせの数を計算する式は非常に急です：

次のように考えてください：

最初の文字にはいくつの選択肢がありますか？ 4：4_ _ __。

2番目は？ 3：4⋅3__。

このように続けると、合計4⋅3⋅2⋅1= 4！= 24の選択肢があることがわかります。 –MrRicci

単語に対して関数を実行する「百科事典」をクライアント側で実行すると、確実にページがクラッシュします。それで、それを修正するために、私はいくつかの考えをしました。

私と一緒に-これはあなたが読むにつれてますます関連性が高くなります。

実際の単語を生成してみたかった（codezを楽しんで）

Anアナグラムは単語遊びの一種であり、単語またはフレーズの文字を再配置して、元のすべての文字を1回だけ使用して、新しい単語またはフレーズを生成した結果です-Wikipeda

アナグラムについて考えるとき、結果は本物の単語またはフレーズであると思います。さて、このコードレビューの目的はコードの機能を変更することではありませんが、私はそれを楽しみたいと思っています。そこで、結果から実際の単語アナグラムを除外して印刷できるソリューションを探すことにしました。

ついにのプレーンテキスト文字列を追跡しました。 em> 〜130,000英語の単語を単語リストとして使用するには、このリストをJSに変換する必要がありました。そこで、各スペースで文字列をスライスし、キー付きプロパティを持つオブジェクトの構造を出力する関数を作成しました。これにより、worldList["word"] -> returns true if word is valid。

130,000語のリストをJSON文字列としてドキュメントの本文に出力することは、関数と同様に、非常にコストがかかります。

…そして関連性：

ここで、あなたの問題が私が自分で発明した問題と出会う場所です。 どのように処理しますかWebページをクラッシュさせずに非常に高価なループを作成しますか？

可能性を実験して、関数で次のことを実行できるようにする方法を実際に発見しました。時間の経過とともにワークロードのバランスをとることで、130,000語を処理し、任意のサイズの単語を維持する機能

ループが速すぎる場合があります

ループはできるだけ速く作られているため、ほとんどの人に最適です。 Webページでそれらを使用するタスクのしかし、処理しすぎると、ブラウザで処理できなくなります。

そのため、ページで処理できるようにするために、時間の経過とともに作業負荷を分散できるソリューションが必要でした。問題のない高価なループ。

私の解決策は、x回呼び出し、 1〜2ms 反復間の遅延。これにより、ページにループを処理するのに十分な時間が与えられました遅延なしで、単語を処理しました毎回クラッシュする前にC “sまでめちゃくちゃ速い。これは、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 “醜い！その間ずっとが無駄ではなかったといいのですが…

事前に計算されたハッシュ

• “コード”、4 chars： 24件の結果、< = 1ms
• 「コーダー」、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,000万の文字列順列が制限を超えているようです：（

スタックオーバーフローを回避するためにアルゴリズムを再設計したことに気付くでしょう。ルックアップは再帰の外部で実行する必要があります。

アルゴリズムを非同期にし、停止を回避するためにミリ秒ごとにすべてのsay 100,000要素を実行することで、アルゴリズムがクラッシュしない可能性を高めることができます。

コメント

• すごい！これは、私が取り組んでいるジェネレータバージョン’よりもはるかに優れています。 +1 （この答えは受け入れられるべきです。’は、私のジェネレーターソリューションよりもはるかに効率的です。）
• 素晴らしい…ただ素晴らしい。私は本当にこのような。リアルタイムのハーモニージェネレーターソリューションが完成したら（または独自に実装することもできます）、自由にそれを使用して同じことを行ってください。 ‘遅くなりますが、結果はリアルタイムで返され、処理できる単語の大きさに終わりはありません。
• ああ、mjolkaは私たちを打ち負かしました両方とも far 。
• こんにちは。ドメイン内でhtmlとcssと一緒にこのコードを実行するにはどうすればよいですか？私は’この無料のものを使用しています： morsetovoynich.000webhostapp.com

2つのスクリプトを作成しました。

1. 最初のスクリプトは高速ですが、あまり保持できません。
2. 2つ目は遅いですが、無制限の結果を表示できます。

どちらも、私が作成したプロトタイプ（fastPush、fastSplit、fastJoin）を使用します。これらは、標準の方法である分割と結合よりも高速です。 modはコンピューターで可能な最も遅い操作であることがわかっているので、ビット単位を使用して奇数か偶数かを確認します。

最初のスクリプトは、10文字の順列チャレンジで他のスクリプトよりも750ミリ秒以上（平均で）勝っています。 。

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文字を超えて試行するとページが壊れます。

2番目のプログラム（以下の1つ）は、自己呼び出し関数を使用して4e4要素のコンソールチャンクにログインし、チャンクを出力するたびにanagrams配列をクリアし、coもクリアします。 nsole.log各5チャンク（これらの組み合わせを確認するのに十分）。関数を自己呼び出すために、プログラムはsetTimeoutの代わりにsetZeroTimeout（ David Baronのブログ）を使用します。これは、setTimeoutがはるかに遅いためです。

(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` anagramsabc`がa,b,ab,c,ac,bc,abc

divを出力する場合>

回答

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

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

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