🐷

直積を生成するGenerator

2021/03/03に公開

TypeScript

generator

直積

tech

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

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に公開してみました。使ってみてください。

Discussion