Javascript’s generator functions are powerful programing constructs that allows you to “pause” your code execution flow in order to “yield” some computation results to the callers. It is especially useful as a functional way to implement iterators.
In this article, we will illustrate how we can use recursive generator functions to produce an iterator for array combinations. We will first see how to generate n-combinations, and then we will move on to generating all combinations.
Generating n-Combinations
Consider the following array:
const array = [1, 2, 3, 4, 5];We are interested in writing an n-combination iterator function combinationN(), which should produce all the n-combinations of this array.
For instance, the following prints out all the 4-combinations of the array.
[ 1, 2, 3, 4 ]
[ 1, 2, 3, 5 ]
[ 1, 2, 4, 5 ]
[ 1, 3, 4, 5 ]
[ 2, 3, 4, 5 ]
The following prints out all the 1-combinations of the array.
[ 1 ]
[ 2 ]
[ 3 ]
[ 4 ]
[ 5 ]
Now let’s see how we may implement combinationN using a recusrive generator function:
This in fact would look very similarly to a normal recursive function that returns all n-combinations at once, because after all we are basically using the same strategy to produce n-combinations by recursively computing all n-1 combinations first. The only difference is that we yield values instead of returning values in generator functions.
Lines 2–7 specifies the base condition of the recursion, where when we want to produce 1-combination of the array, we simply yield each element one after another. In generator functions, yielding a value is akin to returning a value in a normal function, with the critical distinction that yielding does not get you out of the execution flow of the function but merely pauses the flow. In our example, the first yield produces the array value [1] to the caller, and pauses the execution at line 4. When the caller calls the function again, the execution resumes and we will proceed to line 5, which continues the loop. We will only reach line 6, the return statement, after the caller calls combinationN five times, by then the for loop from line 3–5 has finished.
Line 6 illustrates the different style of execution flow of generator functions compared with normal functions. Without the return statement, after the for loop in line 3–5 finishes, the execution would have continued. Since in our implementation we do not provide a base condition for 0-combinations, the recursion would not terminate, and you would have gotten a “maximum stack reached” error.
In line 10–11, we recursively iterate on combinationN, which produces the n-1 combinations of the subarray array.slice(1). And then we can simply yield all the n-combinations by concatenating array[0] with the n-1 combinations.
Generating All Combinations
With an similar recursive strategy, it is easy to implement a generator that produces all combinations:
However, since we are yielding results as soon as we get our sub-combinations, the order produced by this generator is not very intuitive.
[ 1 ]
[ 2 ]
[ 1, 2 ]
[ 3 ]
[ 1, 3 ]
[ 2, 3 ]
[ 1, 2, 3 ]
…
[ 2, 3, 4, 5 ]
[ 1, 2, 3, 4, 5 ]
Generating All Combinations Ordered
An easy way to generate ordered combinations is of course to reuse our combinationN generator.
We now have ordered combinations:
[ 1 ]
[ 2 ]
[ 3 ]
[ 4 ]
[ 5 ]
[ 1, 2 ]
[ 1, 3 ]
…
[ 1, 3, 4, 5 ]
[ 2, 3, 4, 5 ]
[ 1, 2, 3, 4, 5 ]
What is interesting here is that line 18 uses “yield *”, which is a convenient way of saying to yield all that combinationN produces without having to explicitly iterate over it in the code.
Conclusion
In this article, we illustrate one way to implement array combination iterators using generator functions. Javascript’s generator function is a great functional way to provide iterators, among other uses. Implementing iterators usually fits better with object-oriented implementations as we would have need to keep the state of iterations explicitly. Generator functions essentially take this burden away from us!
