C言語による最新アルゴリズム事典
 奥村晴彦

ちょっと必要に迫られたので、JavaScript用のやつを作りました。

こんな感じで使います。





Ruby には最初から Array#combination と Array#permutation が入っていますし、Python には itertools が「バッテリー」に入ってますし、Perlには Math::CombinatoricsをはじめCPANにこの手のモジュールがいくらでもあるのですが、JavaScriptの「これだ」がなかったので。


で、何をもって「これ」なのかというと…


    

  • ジェネレータとして実装 -- 全ての冪集合/順列/組み合わせを配列の配列として返すのであれば、再帰を使って比較的簡単に実装できます。この記事でもそうしてますね。しかしこれだと要素数n個の配列で、順列だとn!個、冪集合では何と2n個の要素が入った配列を一度に生成するはめになります。お姉さんに顔向け出来ません。
    • 

  • コルーチンがあれば、再帰でジェネレーターを書くのも容易で、要はreturnをyieldに変えるだけでいいのですが、残念ながらサポートしているのはFirefoxだけです。
    • 



というわけで再帰を使わずにどう実現したか。これが以外と大変でした。


冪集合


これが一番簡単です。要素数Nに対し0から2N-1までのカウンターを用意し、その二進数表現に対応する要素だけをつまみ上げれば、カウンターに対応した冪集合の要素配列が得られます。


組み合わせ


簡単な方法として、冪集合の中から要素数が指定通りのもののみ抜き出すというやり方もありますが、これはいかにも効率が悪い。例えばnC1はたかだかn個ですが、このn個を取り出すために2n回"grep"しなければならないというのは時間的に富豪すぎる。


ここでは「C言語による最新アルゴリズム事典」(といっても20年ものの)「組み合わせ生成」(P.60)の方法を使いました。なぜこれでうまく行くのかは「ハッカーのたのしみ」を参照かな。要はpopcntが同じで、その次に大きい数を定数時間で計算するというものです。それさえ得られれば、あとは冪集合の場合と同じ方式が使えます。


順列


これが一番込み入っているかな。なぜうまく行くのか大変説明しにくいのですが、ここでは階乗進法という記法を応用しています。



一旦階乗進法表記に直した上で、上の桁に対応する要素を取り出し…というのを桁数だけ繰り返します。まさにspliceの面目躍如です。


しかしそのままでは全要素の順列列挙、つまり順列される配列の大きさが元配列と同じ場合しかうまく行かないので、ここでは一旦組み合わせを作った上で、その組み合わせに対して順列を生成するというやり方をしています。


その他、ジェネレーターを数値として評価すると要素数が帰ってくるなど、JavaScriptっぽい工夫も盛り込んであります。


Enjoy!


Dan the Combinatory Blogger

combinatorics.js