6.2.3 Print Permutations

In this example, you will have an opportunity to take a look at a more detailed, but common recursive problem: Permutations.

Recall that permutations take a set of values and prints out all the possible sequences of the values. In this case, this example takes a list of letters and prints out all the combinations to get to a specific length.

Example: Given a set of values[A, B, C] what are all the 2 character permutations?

AB
AC
BA
BC
CA
CB

Base Case

What is the base case? In this case, the base case will be when we get a string that has the same length as our target length. Until you get there, you will keep adding letters. Since this is a procedural recursive function, once you get to your base case, you will print out the results.

Recursive Call

To accomplish this task, the function will actually make several recursive calls from a for loop. Take a look at the header of this example:

void permute(string soFar, string rest, int length)

Notice that the header has two strings, soFar and rest. The soFar string represents the current permutation that is being built. This is the one that gets checked against the length to meet the base case.

rest holds all the remaining letters that have not been put into the soFar string. To create the permutation, you will add each one of the letters from the rest string to the soFar string one at a time. After you add one, you remove it from rest and make the recursive call with the expanded soFar and the shrunken rest.

Walk Through Example

Take a look at this walk through using the [A, B, C] and length of 2 that you saw above.

When the function is first called, soFar is empty and rest contains ABC.

The base case is not met, so you loop through each of the letters in rest. On the first pass of the loop, A is added to soFar and then called recursively with rest containing BC. The second pass calls B with AC and then the third pass calls C with AB.

In the next round, there are the three recursive calls from above. In all three calls, the base case is still not met, so the program loops. In the first call above, B is added to A to create a soFar of AB and then it is called recursively with a rest of C. The second loop of that first call sees a soFar of AC and a rest of B.

Each of those two recursive calls will meet the base case since the soFar string is now a length of two. They then print out AB and AC respectively, and make no more recursive calls.

Similar recursive calls are made for the second round with the B and C recursive calls. In total, 6 recursive calls are being made.

Kickoff Function

This example also uses a kickoff function. As mentioned before, the idea behind the kickoff function is that it can hide the implementation details that the user doesn’t really need to know. All they need to do is specify the list of available letters and the string length. They don’t need to know that there is a soFar and rest string.

Try This Example