直積を生成するGenerator

1 min read読了の目安(約1000字

直積を生成するワンライナーとして、

const cartesian = (...args) => args.reduce((acc, cur) => acc.flatMap((x) => cur.map((y) => x.concat([y]))), [[],]);
cartesian([1, 2], [3, 4]) // => [[1,3], [1,4], [2,3], [2,4]]

などが知られています。

これは見てのとおり事前に全ての直積をメモリに保存するので、指数関数的にメモリ使用量が増加する直積とはとても相性が悪いです。例えば10要素の配列5つを引数に渡せば 10^5で10万個、10個なら10^{10}で100億になります。

また、直積を先頭から順番に探していって、目的に見合う組を1つだけ見つけたいという用途の場合、事前に全て生成してしまうのは計算の無駄です。

なのでGeneratorを使って書きました。

export function* cartesian(
  ...args: number[][]
): Generator<number[], void, undefined> {
  if (args.length === 0) yield [];
  else {
    const [head, ...rest] = args;
    for (const h of head) {
      const restIter = cartesian(...rest);
      for (const r of restIter) {
        yield [h, ...r];
      }
    }
  }
}
const prod = cartesian([1, 2], [3, 4]);
expect(prod.next().value).toEqual([1, 3]);
expect(prod.next().value).toEqual([1, 4]);
expect(prod.next().value).toEqual([2, 3]);
expect(prod.next().value).toEqual([2, 4]);

みたいに動きます。

練習もかねてnpmに公開してみました。使ってみてください。

https://www.npmjs.com/package/cartesian-generator