cartesian-generator v0.0.4
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.