JavaScriptでデカルト積

javascript

JavaScriptでリスト内包表記のような事をやってみたい。
その為にまずデカルト積をとる為の処理を作成してみる。

デカルト積って？

デカルト積とは直積とも呼ばれ英語ではproduct Cartesian product というようだ。
例えば[1,2,3]という集合と [4,5,6] という集合があると、
これらのデカルト積は
[1,4],[1,5],[1,6],[2,4],[2,5],[2,6],[3,4],[3,5],[3,6]
となる。要するに全ての組み合わせという事。
パッと見た感じ単純に２次元配列にして、ループをネストにするだけで良さそうだが、せっかくなので関数指向的に書いてみたい。


まず２次元目の配列 [4,5,6] に何らかの処理を適用する事で、
[4,5,6] -> [ [1,4],[1,5],[1,6] ]
と変化する処理が必要。
何らかの処理とは固定された1とそれぞれの要素をペアにするという処理。
これをやる為にmap関数を作成。Arrayを拡張する記法にする。

Array.prototype.map = function(f) {
    if (this.length == 0) return this;
    return [f(this[0])].concat(this.slice(1).map(f));
};

var m = 1;
[4,5,6].map(function(n) { return [m, n] }); // [[1,4],[1,5],[1,6]]

この結果を１次元目の配列にそれぞれ適用する。

[1,2,3].map(function(m) {
  return [4,5,6].map(function(n) { return [m, n] });
});
// [[1,4],[1,5],[1,6]], [[2,4],[2,5],[2,6]], [[3,4],[3,5],[3,6]]

このままでは３次元配列なので、これをフラットにしてあげる必要がある。


フラットにする関数もArray拡張で。

Array.prototype.flatten = function() {
  if(this.length == 0) return this;
  return this[0].concat(this.slice(1).flatten());
};

var ary = [[[1,4],[1,5],[1,6]], [[2,4],[2,5],[2,6]], [[3,4],[3,5],[3,6]]];

ary.flatten(); // [[1,4],[1,5],[1,6],[2,4],[2,5],[2,6],[3,4],[3,5],[3,6]]


あとはこれを繋げて、

function product(ary1, ary2) {
    return ary1.map(function(m){
        return ary2.map(function(n){ return [m, n] });
    }).flatten();
}
product([1,2],[3,4]) //[[1,3], [1,4], [2,3], [2,4]]

できたー。

より一般化する

けどこのままでは３つ以上の集合でデカルト積はとれないので、
productに渡された引数全てに再帰的に処理できるよう考え直してみる。


考え方としては最後の２つの直積と手前の１つの直積とそのまた手前の・・・。
って感じでいいと思う。
product(a,b,c,d,e)と５個のリストが渡された場合、
A = product(e)
B = product(d, Aの結果)
C = product(c, Bの結果)
D = product(b, Cの結果)
product(a, Dの結果) が最終的な処理結果。
といったイメージ。

この事から再帰の終了判定はリストを１つだけ渡された時なのでまずはここを確定。

if(arguments.length == 1) return arguments[0];

次に引数が２つ以上の場合は先頭の配列を残して、
後ろの部分だけで再帰的にデカルト積をとっておく。

var rest = Array.prototype.slice.call(arguments, 1);
var rprod = product.apply(null, rest);

この時、sliceされた引数をそのままproductの引数にしてしまうと、
その呼び出されたproduct側では１引数で呼び出された事になってしまうので、
applyを使って引数展開してやる。


次に残しておいた先頭の配列と再帰から返ってきた配列とのデカルト積をとれば良いが、
[m, n]としてしまうと返ってきた方の配列の要素が配列である為、
[ [1, [3,5] ]というようになってしまう。
なのでプリミティブ、配列どちらでもフラットに結合してくれるconcatを使って回避。

return [m].concat(n);

あとはこれを繋げると完成。

function product() {
    if(arguments.length == 1) return arguments[0];
    var rprod = product.apply(null, Array.prototype.slice.call(arguments,1));
    return arguments[0].map(function(m){
        return rprod.map(function(n){ return [m].concat(n) });
    }).flatten();
}

動作チェック in Firebug

product([1,2,3],[4,5]);
//⇒[[1, 4], [1, 5], [2, 4], [2, 5], [3, 4], [3, 5]]

product([1,2],[3],[4,5,6]);
//⇒[[1, 3, 4], [1, 3, 5], [1, 3, 6], [2, 3, 4], [2, 3, 5], [2, 3, 6]]

うん、いけてるね。

明日は

これを使って内包表記に挑戦するぞ。


しかしLispっぽい再帰ばっかでJavaScriptだとすぐにスタックが溢れそう。。。
まぁ見やすさ重視ってことで。
再帰のとこをループにしてやればある程度実用的になるかな。


おまけ

Arrayの汚染が気に食わない場合はこっち。
再帰もループ化。

var product = (function() {
    function map(ary, f) {
        for(var i = 0,res = []; i < ary.length; i++) {
            res.push(f(ary[i]));
        }
        return res;
    }
   
    function flatten(ary) {
        for(var i = 0,res = []; i < ary.length; i++) {
            res = res.concat(ary[i]);
        }
        return res;
    }

    return function() {
        if(arguments.length == 1) return arguments[0];
        var rprod = product.apply(null, Array.prototype.slice.call(arguments,1));
        return flatten(map(arguments[0], function(m){
            return rprod.map(function(n){ return [m].concat(n) });
        }));
    };
})();