Array Combination Iteration with Javascript Generator Function

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

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

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

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