Permutations

In "Problems for Computer Solution" by Fred Gruenberger and George Jaffray, permutation was a topic for one of the problems.

Now everyone that has made it through the most basic classes in computer science had a class that at least touched on the concept of combinations and permutations. For those that have never take computer math class, permutation is the concept of showing every sequence that can be created using every element in the set only once.

For example: A set containing three characters, 'A', 'B' and 'C'. There are six different permutations of this set: 'ABC', 'ACB', 'CAB', 'BAC', 'BCA', 'CBA'

Click here for a more complete description of Permutation

If you add another character 'D' the number of permutations go to 24. So that pattern goes:

1 character = 1 permutation
2 characters = 2 permutations
3 characters = 6 permutations
4 characters = 24 permutations

Now anyone see the pattern? 1 x 2 x 3 x 4? Or 4! (factorial). Another way to write 4! is 4 x (3 x (2 x 1)) or 4! = 4 x 3! Basic computer science professors use factorials as the basic example in recursion.

private int Factorial(int Number)
{
    if(Number == 0) return 1;
    else return Number * Factorial(Number - 1);
}

The problem in the book does not involve factorials but the actual generation of all the possible permutations of the elements in the set. I've already hinted that it involves recursion, can you figure it out?

Take a few minutes before reading any further.

OK, if you got it then good for you. now implement it. While your doing that, I'll explain it to everyone else.

So, if we are going to use recursion we need to take into account two things:

1. Solving a subset of the problem helps solve the entire problem
2. There must be a base case where the answer is known

Lets take the second point first. If a set only contains a single element then that set can only have a single permutation, so this can be our base case.

Next, how can a subset of the problem help solve the entire problem? It may be easier to understand in an example:

If you have the set 'A' 'B', all the permutations are are: 'AB' and 'BA'.

If you now add the character 'C', you can take each previous permutation and add the new character to the front of the string. Then you just cycle the new letter through each position in the string until it is at the end. A manual example looks like this:

C AB - A C B - AB C
C BA - B C A - BA C

The book suggests you write separate functions for a single character string, a two character string, a three character string and a four character string with the four first calling the three which first calls the two which first calls the single character string function.

Once you get to writing the three and four character string function you will notice that 99% of your code looks the same in these two functions. Now you can, if it does not do so already, alter the two character function to work just like the three and four character functions.

Now you should be able to roll these all together to get a recursive function that generates all permutations of a string of any length.

But, this is dot net! We are object oriented, so we should be able to now alter the function to accept an array of object arrays and output a new array of object arrays. Through in a little bit of generics and you will have a completely reusable permutation generator!

This was a fun little function to write and it got my recursive juices flowing. Maybe I'll attack a simple maze generator and solver next! Who knows?