JavaScriptで複数の配列からすべての組み合わせ（デカルト積）を生成する方法

JavaScriptで複数の配列から組み合わせを生成する

JavaScriptでは、要素数の異なるn個の配列から、それぞれの配列から1つずつ要素を選び出し、そのすべての組み合わせ（デカルト積）を生成したいケースがあります。本記事では、配列の個数が可変でも対応できる汎用的な実装方法を解説します。

扱うデータの例

まず、次のようなデータを考えてみましょう。

const arr = [
    [0,1],
    [0,1,2,3],
    [0,1,2]
]

このデータは3つのサブ配列を持っており、それぞれの配列には異なる数の要素が含まれています。ここでやりたいのは、各配列から1つずつ要素を取り出して組み合わせ、そのすべてのパターンを取得することです。

期待される出力のイメージは以下のとおりです。

0,0,0 // 配列0の要素「0」、配列1の要素「0」、配列2の要素「0」
0,0,1
0,0,2
0,1,0
0,1,1
0,1,2
0,2,0
0,2,1
0,2,2

このように、各配列の要素を順番に組み合わせた結果がすべて列挙されていきます。

なぜハードコーディングでは不十分なのか

もし配列の数が常に固定であれば、ネストしたループなどを用いた決め打ちの実装でも簡単に対応できます。しかし実際の開発では、配列の数は状況によって変動することが少なくありません。

const arr1 = [[0,1], [0,1]];
const arr2 = [[0,1,3,4], [0,1], [0], [0,1]];

上記のように、2つの場合もあれば4つの場合もあります。こうした可変的な入力に柔軟に対応するためには、再帰処理を活用した汎用的な関数を実装するのが効果的です。

再帰を使った実装例

それでは、実際のコードを見ていきましょう。

const arr = [
    [0,1],
    [0,1,2,3],
    [0,1,2]
]
const combineAll = (array) => {
    const res = [];
    let max = array.length−1;
    const helper = (arr, i) => {
        for (let j=0, l=array[i].length; j<l; j++) {
            let copy = arr.slice(0);
            copy.push(array[i][j]);
            if (i==max)
            res.push(copy);
            else
            helper(copy, i+1);
        };
    };
    helper([], 0);
    return res;
};
console.log(combineAll(arr));

コードの仕組み

• combineAll関数： 結果を格納する配列 res を用意し、補助関数 helper を初期状態 ([], 0) で呼び出します。
• helper関数： 引数 i は現在処理中の配列のインデックスを表します。array[i] の各要素に対してループを行い、これまでの組み合わせをコピーした新しい配列に現在の要素を追加していきます。
• 終了条件： 最後の配列（i == max）まで処理が進んだ時点で、完成した1つの組み合わせを結果配列に格納します。そうでなければ、自身を再帰的に呼び出して次の配列へと処理を進めます。

実行結果

このコードをコンソールで実行すると、次のような出力が得られます。

[
    [ 0, 0, 0 ], [ 0, 0, 1 ],
    [ 0, 0, 2 ], [ 0, 1, 0 ],
    [ 0, 1, 1 ], [ 0, 1, 2 ],
    [ 0, 2, 0 ], [ 0, 2, 1 ],
    [ 0, 2, 2 ], [ 0, 3, 0 ],
    [ 0, 3, 1 ], [ 0, 3, 2 ],
    [ 1, 0, 0 ], [ 1, 0, 1 ],
    [ 1, 0, 2 ], [ 1, 1, 0 ],
    [ 1, 1, 1 ], [ 1, 1, 2 ],
    [ 1, 2, 0 ], [ 1, 2, 1 ],
    [ 1, 2, 2 ], [ 1, 3, 0 ],
    [ 1, 3, 1 ], [ 1, 3, 2 ]
]

このように、再帰を利用することで配列の個数や要素数がどのように変わっても、すべての組み合わせを自動的に生成できる汎用的な関数を実現できます。選択肢の組み合わせ列挙や検索条件の網羅など、さまざまな場面で応用できるテクニックなので、ぜひ覚えておきましょう。