functional programming
This question is tagged functional-programming so let's take a look at the List monad:
One application for this monadic list is representing nondeterministic computation. List
can hold results for all execution paths in an algorithm...
Well that sounds like a perfect fit for cartesian
. JavaScript gives us Array
and the monadic binding function is Array.prototype.flatMap
, so let's put them to use -
const cartesian = (...all) => {
const loop = (t, a, ...more) =>
a === undefined
? [ t ]
: a.flatMap(x => loop([ ...t, x ], ...more))
return loop([], ...all)
}
console.log(cartesian([1,2], [10,20], [100,200,300]))
[1,10,100]
[1,10,200]
[1,10,300]
[1,20,100]
[1,20,200]
[1,20,300]
[2,10,100]
[2,10,200]
[2,10,300]
[2,20,100]
[2,20,200]
[2,20,300]
more recursion
Other recursive implementations include -
const cartesian = (a, ...more) =>
a == null
? [[]]
: cartesian(...more).flatMap(c => a.map(v => [v,...c]))
for (const p of cartesian([1,2], [10,20], [100,200,300]))
console.log(JSON.stringify(p))
.as-console-wrapper { min-height: 100%; top: 0; }
[1,10,100]
[2,10,100]
[1,20,100]
[2,20,100]
[1,10,200]
[2,10,200]
[1,20,200]
[2,20,200]
[1,10,300]
[2,10,300]
[1,20,300]
[2,20,300]
Note the different order above. You can get lexicographic order by inverting the two loops. Be careful not avoid duplicating work by calling cartesian
inside the loop like Nick's answer -
const bind = (x, f) => f(x)
const cartesian = (a, ...more) =>
a == null
? [[]]
: bind(cartesian(...more), r => a.flatMap(v => r.map(c => [v,...c])))
for (const p of cartesian([1,2], [10,20], [100,200,300]))
console.log(JSON.stringify(p))
.as-console-wrapper { min-height: 100%; top: 0; }
[1,10,100]
[1,10,200]
[1,10,300]
[1,20,100]
[1,20,200]
[1,20,300]
[2,10,100]
[2,10,200]
[2,10,300]
[2,20,100]
[2,20,200]
[2,20,300]
generators
Another option is to use generators. A generator is a good fit for combinatorics because the solution space can become very large. Generators offer lazy evaluation so they can be paused/resumed/canceled at any time -
function* cartesian(a, ...more) {
if (a == null) return yield []
for (const v of a)
for (const c of cartesian(...more)) // ⚠️
yield [v, ...c]
}
for (const p of cartesian([1,2], [10,20], [100,200,300]))
console.log(JSON.stringify(p))
.as-console-wrapper { min-height: 100%; top: 0; }
[1,10,100]
[1,10,200]
[1,10,300]
[1,20,100]
[1,20,200]
[1,20,300]
[2,10,100]
[2,10,200]
[2,10,300]
[2,20,100]
[2,20,200]
[2,20,300]
Maybe you saw that we called cartesian
in a loop in the generator. If you suspect that can be optimized, it can! Here we use a generic tee
function that forks any iterator n
times -
function* cartesian(a, ...more) {
if (a == null) return yield []
for (const t of tee(cartesian(...more), a.length)) // ✅
for (const v of a)
for (const c of t) // ✅
yield [v, ...c]
}
Where tee
is implemented as -
function tee(g, n = 2) {
const memo = []
function* iter(i) {
while (true) {
if (i >= memo.length) {
const w = g.next()
if (w.done) return
memo.push(w.value)
}
else yield memo[i++]
}
}
return Array.from(Array(n), _ => iter(0))
}
Even in small tests cartesian
generator implemented with tee
performs twice as fast.
d3.cross(a, b[, reducer])
in February. github.com/d3/d3-array#cross