While working on a different project, I came across this puzzle.
Given a set of values, compute its full set of combinations.
Note that a “Combination” is a group of values where order of the values does not matter. Ex: ‘123’
We are NOT computing a set of “Permutations”. Ex: ‘123’ and ‘213’ and ‘321’ etc.
So, for example, we want to compute the set of combinations for the values 1,2,3 we can easily list them out by hand.
1, 12, 13, 14, 123, 124, 134, 1234, 2, 23, 24, 234, 3, 34, 4
There are 2^(n)-1 or 15 total combinations. Easy enough right?
What about values 1 to 5? That’s 31 combinations.
what about values 1 to 999? I’d spend the rest of my lifetime writing out that list.
How do we write a program to do this for us?
We know we need a loop for the most significant digit… and going deeper, we assume we need another loop for the second most significant digit… deeper still means more loops… MOOAARR LOOPS.
Writing 999 loops is definitely easier than writing out each combination by hand, but I still don’t want to write out 999 loops.
If we were only computing a single value result, we might think about solving this problem mathematically and avoid loops altogether. But instead, we need to record a combination at each step of the process.
The technique for solving these types of “loops on loops on loops” problems is called “Recursion”.
What recursion in programming looks like is a function, that during its execution, calls itself.
We can use a recursive function to perform our loops within loops within loops and record a combination at each step.
Solving the problem.
Let’s start our program by defining our
end values from the first example above.
We’ll also create a Vec that will hold our result.
For the meat and potatoes of our program, we need a loop that serves the purpose of “given a number, calculate all combinations of values >= this number”. Ex: Given 1, calculate 1, 12, 123, 1234, 13, etc.
Inside of the loop, we’ll put our recursive function… the recursive function… the recursive…
What kind of recursive function will solve this problem?
Since each call to the recursive function needs to know the part of the problem it’s supposed to work on, we need to give it the current position of the overall problem. We’ll call it
pos for position. Ex.
pos of ‘2’ will work on 2,23,234,24
We also need to keep track of the history of numbers that came before our recursive function call. We’ll call that history
pos is ‘3’, then
prefix could be ‘1’ or ‘12’ or ‘2’.
We need to know how many times we need to repeat the inner loops ( current position to the end), so we’ll keep passing the
end variable we created earlier.
Finally, we need a place to record our results from each step. We’ll pass a reference to our mutable
collections vector along as well.
The code for the recursive function ends up looking like this:
Putting it all together into a working program…
The result comes out just as we wanted. By printing the Collection we see it contains all combinations for the values 1 to 4.
Recursive functions are great for solving these types of problems.
Because we retain and build data at each step of the recursion, we quickly consume a large amount of memory as the value of