【JavaScript】複数の配列からダッシュ区切りのデカルト積を生成する方法

はじめに

JavaScriptでは、任意の個数の配列を受け取り、それぞれの配列から要素を1つずつ選んだすべての組み合わせ(デカルト積)を求めたいケースがあります。本記事では、組み合わせた要素をダッシュ(−)で連結した文字列の配列として返す関数の実装方法を解説します。

デカルト積とは

デカルト積(直積)とは、複数の集合から要素を1つずつ取り出して作られる、すべての順序付き組み合わせのことです。例えば [a, b] と [1, 2] のデカルト積は、「a-1」「a-2」「b-1」「b-2」の4通りになります。配列が3つになれば、それぞれの要素数を掛けた数だけ組み合わせが生まれます。

実装例

以下のコードでは、可変長引数(...arrs)で任意の個数の配列を受け取り、reduce と map を組み合わせてデカルト積を計算しています。

const arr1 = ['a', 'b', 'c', 'd'];
const arr2 = ['1', '2', '3'];
const arr3 = ['x', 'y'];

const dotCartesian = (...arrs) => {
  const res = arrs.reduce((acc, val) => {
    let ret = [];
    acc.map(obj => {
      val.map(obj_1 => {
        ret.push(obj + '−' + obj_1);
      });
    });
    return ret;
  });
  return res;
};

console.log(dotCartesian(arr1, arr2, arr3));

コードの解説

• 可変長引数(...arrs):呼び出し時に渡されたすべての配列が、arrs という1つの配列にまとめられます。引数の個数が固定されないため、2つの配列でも10個の配列でも同じ関数で扱えます。
• reduce:配列を先頭から順に処理し、それまでの累積結果(acc)と次の配列(val)を掛け合わせるように新しい組み合わせを生成していきます。
• ネストしたmap:既存の各組み合わせ(obj)に対して、次の配列の各要素(obj_1)をダッシュで連結した新しい文字列を生成し、結果配列に追加します。

処理の流れを見てみましょう。まず最初の配列 ['a', 'b', 'c', 'd'] が初期値となります。次に2番目の配列と組み合わさり、「a-1」〜「d-3」までの12通りが生成されます。最後に3番目の配列と組み合わさり、24通りの結果が完成します。

実行結果

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

[
  'a−1−x', 'a−1−y', 'a−2−x',
  'a−2−y', 'a−3−x', 'a−3−y',
  'b−1−x', 'b−1−y', 'b−2−x',
  'b−2−y', 'b−3−x', 'b−3−y',
  'c−1−x', 'c−1−y', 'c−2−x',
  'c−2−y', 'c−3−x', 'c−3−y',
  'd−1−x', 'd−1−y', 'd−2−x',
  'd−2−y', 'd−3−x', 'd−3−y'
]

4 × 3 × 2 = 24 通りの組み合わせが、元の配列の並び順に従って整然と生成されていることが確認できます。

別解:flatMap を使った簡潔な書き方

ES2019以降で利用できる flatMap を使うと、ネストした map を1段階にまとめて、より読みやすく記述できます。

const dotCartesian = (...arrs) =>
  arrs.reduce((acc, val) =>
    acc.flatMap(a => val.map(b => `${a}−${b}`))
  );

console.log(dotCartesian(arr1, arr2, arr3));

動作は先ほどのコードと完全に同じですが、一時的な配列宣言が不要になり、意図もひと目で分かりやすくなります。

注意点

• この実装では配列が1つだけ渡された場合、その配列がそのまま返されます。常に統一した形式が必要な場合は、reduce の第2引数に初期値 [''] を渡すなどの工夫を検討してください。
• 結果の件数は各配列の要素数の積になるため、要素数が大きい配列を多数組み合わせると、結果の配列が爆発的に増大します。大量データを扱う場合はメモリ使用量とパフォーマンスに注意しましょう。

まとめ

reduce と map(または flatMap)を組み合わせることで、任意の個数の配列からダッシュ区切りのデカルト積をシンプルに生成できます。組み合わせ検索やテストケースの自動生成など、さまざまな場面で応用できるテクニックなので、ぜひ覚えておきましょう。