総当りの配列を返す関数の作成

質問

総当りの配列を返す関数の作成が上手くいきません。
関数にしてほしいことは、与えられた配列arrからnum個取り出す組み合わせを配列で返してもらうことです。

下記が例です。関数の名前をtotalHitとします。
********************************************
var arr = [0,1,2,3,4];
var num = 2;
var arr2 = totalHit(arr,num);
/*
arr2に[[0,1],[0,2],[0,3],[0,4],[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]が
代入されてほしい
*/
********************************************
ネットでもずいぶん探しましたが、目的のものは見つかりませんでした。
アルゴリズムが分かる方、ヒントでもかまいませんので、ご教示願います。

回答No.2

yuu_x · ベストアンサー

樹形図を書き出してみると分かりやすいかと思いますが、きれいなツリー構造をしているので、再起関数でできると思いますよ。

例えば、[0, 1, 2, 3] から 3 つを選ぶ場合の、樹形図は(掲示板の関係少し見ずらいかもしれません)
0-1-2
|*|-3
|-2-3

1-2-3

というツリーが出来上がります。ツリー構造の場合、隣と下を順にたどっていけば、全ての枝を通ることができます。
例えば、最初の 0 の位置の場合、隣の 1 と 下の 1 を発火させます。
隣の 1 はさらに隣の 2 と下の 2 を発火。後は適度に終了判定を入れるだけです。

function totalHit(ary, num){
var r = [];

(function(m, n, p, c){
if(n < 1){
r.push(c);
}else if(m - p >= n){
arguments.callee(m, n - 1, p + 1, c.concat(ary[p])); // 下のノード
arguments.callee(m, n, p + 1, c); // 隣のノード
}
})(ary.length, num, 0, []);

return r;
}

引数の p は現在位置、m は配列数、n は取り出す個数（ツリーの下へ行くほど、取り出す個数は減っていきます）
先の例の場合、最初の n は 3、ひとつ下の n は 2 という具合です。
最後の c は組み合わせごとの部分配列です。

もう少し実行速度を上げれると思いますので、色々工夫してみてください。

お礼

樹形図が良く分からなかったのですが、多分
０－１－２
｜　└－３
└－２－３
１－２－３
ということですよね？

関数を実行したことろ、上手くいきました。
arguments.calleeなど、知らない関数(?)もあるので、これを期に、
もっと知識を増やして以降と思います。

ありがとうございました。

回答No.1

zxcv0000

あなた自身、[[0,1],[0,2],[0,3],...] という答えを得る作業をすでにされていますね、頭の中で。

まず先頭の 0 を軸にして他と組み合わせる。
次に 1 を軸にして自分より右にあるものと組合せる。
後も同様に、自分より右にあるものと組合せる。

これを JavaScript で書けば、すでに出来てるじゃないですか。

「自分より右にあるものと組合せる。」は、実は先頭の 1 や 2 にも適用可能で、その時ルールは「自分より右にあるものと組合せる。」以外何も要らない事に気付けば、スマートなコードになります。

お礼

それは分かるのですが…
function totalHit(arr,num){
　var returnArr = [];
　for(i=0;i<arr.length;i++){
　　for(j=i+1;j<arr.length;j++){
　　　...
　　}
　}
　return returnArr;
}

numの値によって、for文の個数が変化してしまうと思うのです。
どうすればいいのでしょうか？？