Cartesian Generator

Produce cartesian product using generator.

Motivation

You can produce cartesian product in a single-line code. such as:

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]]

Although this is concise and easy to copy&paste, this functional-way has some problems.

This way...

1. uses so much memory, because cartesian product increase exponentially. This may cause memory leak.
2. needs time to produce entire result beforehand.
3. causes unnecessary computation, especially you want to find certain tuple(element of cartesian product) that matches your demand. Because this way produces entire result beforehand

That's why I implemented cartesian product with generator.Generator produces next tuple when it is necessary.

How to use

yarn add cartesian-generator

or simply paste following code.

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];
      }
    }
  }
}

To use:

import { cartesian } from "cartesian-generator";
const prod = cartesian([1, 2], [3, 4]);
for (const p of prod){
    console.log(p) // [1,3], [1,4], [2,3], [2,4]
}

Benchmark

function version vs generator version(this package).

I tested these two ways with 7 arguments that contains 10 elements, so length of cartesian product is 10^7.You can see code at bench.js.

version	time(ms)
function	6862
generator	5950

14% faster!!

When I tried bench with more arguments, function version caused memory leak, unlike generator.