Permutation Generator

Permutations come up from time to time in contest problems, and we often take for granted how they are generated. It's not hard to do once you get the hang of it, but you certainly want to get the hang of it before your first competition. I recommend using a recursive algorithm because it is a concise way to write a permutation generator for any size set.

Remember that a permutation is an arrangement or ordering of the elements of a set. If you have the 7 books shown in Figure 1, there are \(7! = 5040\) different ways you can arrange them on a shelf. If we give the books the labels "A" through "G", The first few permutations are \[A B C D E F G\] \[A B C D E G F\] \[A B C D F E G\] \[A B C D F G E\] \[A B C D G E F\] \[A B C D G F E\] \[\vdots\] \[G F E D C B A\]

In this challenge, you will write a generator that works for any number of elements (although in practice, you will not use it for sets of more than 10 or 11).

Challenge

Write a program that will print all the permutations of a set of characters containing numbers or letters. For convenience, count the permutations that you generate and print the total number at the end of the run. This helps you verify that your program is running correctly because you can use the factorial button on your calculator to check your result.

You can embed the set in your program as a pre-defined string, initialised array, or what have you. You should be able to change the set easily, adding or removing elements without having to make any other changes to your program. The sample replits work with strings containing digits or letters, such as "0123456789" or "ABCDEFG". To change the set, you simply have to add or remove characters from the string.

Implementation

I strongly suggest that you use a recursive algorithm to implement your permutation generator. Such an approach will handle sets of any size (although you will not want to use your program for sets larger than 11 due to time and memory constraints) without modification. The business part of your program will also be quite small, requiring no more than 10-15 lines of nicely formatted C++.

A recursive strategy for generating permutations is as follows:

0. Create a container for the permutation (in my case, this is an empty string). Pass the set of elements and the container for the permutation to the generator function.
1. Check the size of the set that has been passed in.
   1. If the set contains only one element, put it in the last position of the container and print the contents of the container in order. Return.
   2. If the set contains more than one element, iterate through them one by one. Put the chosen element in the next position of the container, and pass the container and the subset containing the remaining elements to this function (Step 1). Return after you have gone through all the elements.

For the purposes of illustration, suppose that our set is { 1, 2, 3, 4 }. When we enter the generator function, the container is empty, and we have four elements to place. We choose element 1 and put it in the first position. When we call the generator function again, we are doing so from within the first invocation, and we are passing { 2, 3, 4 } and the container with "1".

In the second invocation, we choose an element 2 and put it in the second position before calling the generator function, again from within the function itself. This creates a third invocation, which receives { 3, 4 } and the container with "12". We now choose the element 3 and put it in third position, leaving us with the subset { 4 } and container "123". We call the generator function from within the third invocation, creating a fourth invocation. At this point, we see that the subset has only one element, so we add it to the container, print "1234", and return.

Returning takes us back to the third invocation, where we now choose the next element, 4. This means we pass { 3 } and "124" to our generator in a new fourth invocation. There, we again see that the set has only one element, so we print "1243" and returns to the third invocation. The third invocation is now out of elements, so it returns us to the second invocation. In the second invocation, we now choose 3, passing { 2, 4 } and "13" to a new third invocation.

Continuing in this manner, we see that the top-level invocation of our generator goes through the four possibilities for the first position: 1, 2, 3, 4. For each of those choices, the second-level invocation chooses among the remaining three elements, and so on down to the bottom-level invocation. At that point the task is so simple we only have to add the remaining element to the container and print the permutation.