A short while back I wrote a post touching upon combinatorics. Part of the code of that article used a Combinator object, which generated combinations of choices and stored them in an array.
The problem with combinatorial operations is that the number of combinations can grow explosively fast with every additional choice added — greater than exponentially fast, in some cases.
If I have three items and allow 0, 1, 2, or 3 of those to be chosen, I get 8 unique choices if I disregard order, allow no repeats and include the null set. Double that to six items and you wind up with 64 choices (8*8). Double that again (12 items), there are 4096 choices (64*64). In this case, with the restrictions noted above, the number of combinations is 2 to the power of n choices, so it grows merely(!) exponentially.
For a large number of items, storing every combination in an array could lead to memory exhaustion. Instead of having the Combinator return an array only after all combinations have been generated, how about if it returned each combo one-by-one, as needed? Since the Combinator is generating combinations, can it be converted to a generator?
Original Combinator.js
In the original code, every combination created by calling combine() is stored in a combinations array:
var Combinator = function (opts) {
var combinations = [];
function combine(current, remainder) {
if (remainder.length === 0) {
if (current.length >= (opts.min || 0) &&
current.length <= (opts.max || current.length))
combinations.push(current);
} else {
combine(current.concat(remainder[0]), remainder.slice(1, remainder.length));
combine(current, remainder.slice(1, remainder.length));
}
return this;
}
return {
combinations: combinations,
combine: combine
}
}
module.exports = Combinator;The algorithm is embellished a bit with the addition of min/max options — these limit the number of combinations that contain at least min, and at most max, elements. I can be used like so:
var menu = {
threeItems: {
min: 0,
max: 3,
values: [1, 2, 3]
}
}
var threeCombos = new Combinator({
min: menu.threeItems.min,
max: menu.threeItems.max
})
.combine([], menu.threeItems.values)
.combinations;The menu.threeItems.values property has (surprise!) three values. The min and max properties determine the set of combinations to be generated. In this case, we ask for sets from 0 length (the null set) to full length (the entire values set). Remember that we’re not interested in order, nor do we allow duplicates. Let see it in action:
console.log('threeCombos.length =', threeCombos.length, threeCombos);
-- output --
threeCombos.length = 8 [ [ 1, 2, 3 ], [ 1, 2 ], [ 1, 3 ], [ 1 ], [ 2, 3 ], [ 2 ], [ 3 ], [] ]Now, instead of using an array to store all combinations, let’s convert this bit of JavaScript to use the new ES6 generator functionality. A generator is a stateful function that yields values one-by-one, in an iterative fashion.
Naive attempt
A generator function is declared using function* instead of function. The yield operator is called within the generator function to return single values back to the caller. The generator remembers the state of the previous call, so subsequent yields will return the next logical value. The caller uses the next() method to get each subsequent value from the generator function. No arrays required!
I can be pretty lazy at times, so I took the tl;dr approach to the JavaScript documentation on generators and just winged it. The first attempt was:
var CombinatorGenerator = function (opts) {
function* combine(current, remainder) {
if (remainder.length === 0) {
if (current.length >= (opts.min || 0) &&
current.length <= (opts.max || current.length)) {
yield(current);
}
} else {
combine(current.concat(remainder[0]), remainder.slice(1, remainder.length))
combine(current, remainder.slice(1, remainder.length))
}
}
return {
combine: combine
}
}This makes sense, right? Instead of pushing a set of choices to an array, I just yield a value. In the client code, I keep calling next() until the generator tells me it’s done.
var menu = require('./menu');
var Combinator = require('./Combinator-generator-naive');
function run() {
var threeCombos = new Combinator({
min: menu.threeItems.min,
max: menu.threeItems.max
})
.combine([], menu.threeItems.values);
for (;;) {
var it = threeCombos.next();
if (it.done) {
console.log("done!")
break;
}
console.log("choice", it.value);
}
}
run();Alas, my hopes were dashed. The output is:
PS C:\Users\Jeff\workspace\Generator> node .\test-generated.js
done!Alright, so obviously the new Combinator is returning before the first yield does, so we’re “done!” before we’re actually done.
Intuitive attempt
Still loathe to read documentation, I next try to intuit the bug fix. So what happens if I just yield from the internal combine calls — logical, no? Instead of:
} else {
combine(current.concat(remainder[0]), remainder.slice(1, remainder.length))
combine(current, remainder.slice(1, remainder.length))
}I try yielding from the recursive calls:
} else {
yield combine(current.concat(remainder[0]), remainder.slice(1, remainder.length)).next()
yield combine(current, remainder.slice(1, remainder.length)).next()
}Truly, this will work. So let’s run it:
PS C:\Users\Jeff\workspace\Generator> node .\generated.js
choice { value: { value: { value: [Object], done: false }, done: false },
done: false }
choice { value: { value: { value: [Object], done: false }, done: false },
done: false }
done!Hmmm…that’s no good — what gets returned are the recursive generators’ state, but not the actual values from the yield operations.
Thoughtful attempt
Okay, time to buckle down. A little googling on “recursive generator” turns up a reference to Python’s yield from. That syntax delegates the yield calls to another generator. Is there an equivalent in JavaScript?
Yes! — and it’s the yield* syntax. This is actually in the document link about generators; had I read it, I possibly would have figured this out sooner (laziness, like crime, doesn’t [always] pay). The correct syntax is:
} else {
yield* combine(current.concat(remainder[0]), remainder.slice(1, remainder.length))
yield* combine(current, remainder.slice(1, remainder.length))
}And now, when I call the combine method, I see:
node .\generated.js
choice [ 1, 2, 3 ]
choice [ 1, 2 ]
choice [ 1, 3 ]
choice [ 1 ]
choice [ 2, 3 ]
choice [ 2 ]
choice [ 3 ]
choice []
done!Good! I’m getting back all the combinations, one-by-one. Success!
Full code used in this post can be found here. Happy generating!
Update 2/26/2017
After reading this article by the indefatigable Eric Elliott, I began to think I had traded one type of resource exhaustion (memory) for another (stack). However, I’ve run the Combinator with an input array of length 30 and it ran to completion: that’s 2³⁰ combinations generated (over a billion). Note that the algorithm
- is not using tail recursion (or maybe it’s ‘split-tail’ recursion?); and
- yield *, according to Eric’s article, should not be optimized as a tail recursive call in any case
Yet, it works. Proof can be found by running generated30.js in the git repository for this post.