JavaScriptで2つの配列のデカルト積（直積）を計算する方法

デカルト積（直積）とは

2つの集合（配列）AとBのデカルト積は「A × B」と表記され、aがAに属し、bがBに属するような、すべての順序対 (a, b) の集合（配列）を指します。

もう少し平易に説明すると、2つの配列のデカルト積とは、「1つ目の要素が最初の配列に属し、2つ目の要素が2番目の配列に属する」という条件を満たす、考えられるすべての2要素ペアの組み合わせのことです。

たとえば、次の2つの配列があったとします。

const arr1 = [1, 2, 3];
const arr2 = [4, 5];

この場合、デカルト積は次のようになります。

const product = [[1, 4], [1, 5], [2, 4], [2, 5], [3, 4], [3, 5]];

ポイントは、最初の配列の各要素に対して、2番目の配列の全要素が順番にペアになるという点です。結果の配列の長さは、2つの配列の長さの積（この例では 3 × 2 = 6）になります。

実装例

この処理は、二重のforループを使うことでシンプルに実装できます。コードは以下の通りです。

const arr1 = [1, 2, 3];
const arr2 = [4, 5];
const cartesianProduct = (arr1, arr2) => {
    const res = [];
    for(let i = 0; i < arr1.length; i++){
       for(let j = 0; j < arr2.length; j++){
          res.push(
             [arr1[i]].concat(arr2[j])
          );
       };
    };
    return res;
};
console.log(cartesianProduct(arr1, arr2));

外側のループで最初の配列の要素を1つずつ取り出し、内側のループで2番目の配列の各要素と組み合わせて、新しい配列として結果に追加していきます。

出力結果

コンソールには以下のように出力されます。

[ [ 1, 4 ], [ 1, 5 ], [ 2, 4 ], [ 2, 5 ], [ 3, 4 ], [ 3, 5 ] ]

flatMapを使ったより簡潔な書き方

ES2019で導入された flatMap() メソッドを使うと、同じ処理をより宣言的で簡潔に記述できます。

const cartesianProduct = (arr1, arr2) =>
  arr1.flatMap(a => arr2.map(b => [a, b]));

console.log(cartesianProduct([1, 2, 3], [4, 5]));
// [[1, 4], [1, 5], [2, 4], [2, 5], [3, 4], [3, 5]]

どちらの方法でも計算量は O(n × m)（n、mはそれぞれの配列の長さ）となるため、配列のサイズが大きくなると結果の要素数が急増することに注意してください。可読性とコードの簡潔さを重視する場合は、flatMapを使った方法がおすすめです。