A simple and fast permutation generator (1)
Today’s article is the first in a series that will deal with generating permutations in a simple and fast manner.
All code samples will be C++. As they are quite simple, they will be easy to write in other languages as well.
About the simple and fast requirements :
- Simple : this was the key requirement for me. Permutations are basically a simple concept, so any algorithm to generate them should reflect this.
- Fast : when simple is done, fast pops up. How could I get the original algorithm as fast as possible without giving up the simplicity?
I must also say that I have done almost no research whatsoever on this subject.
There are is one main reason for this : as the old hacker’s adage says : 6 months in the lab can save you 10 minutes in the library.
On to the algorithm itself. ( In this installment, there will no real code, only the basic concepts and some pseudo-ish-like code. )
When I think of the combination simple, mathematical problems and programming the first thing that pops into my mind is recursion.
Recursion allows you to define problems in a very simple manner, because you tackle one step at a time. It’s a special form of the divide-and-conquer approach to problem solving.
So how does this apply to permutations?
Well lets first take a look at some examples of a permutation. Again, do not expect highbrow mathematical dogma’s and theories, that’s not what I want to talk about, nor would I be able to without extensive research, and like I said, I didn’t do any research.
A permutation is a specific ordering of N-items. In this case an item will be an unsigned integer value. In computer programs, this is sufficient because unsigned integers can be indices into an array, and thus can be used to permutate any sequence of any type of digitally representable objects.
These are permutations of the sequence of unsigned integers : 0,1,2,3,4
How can we generate all permutations of this sequence in a simple manner? Something that you could explain to any reasonbly intelligent person.
Well when looked at from a recursive point of view, you could say that generating all permutations is simply a matter of putting all possible values in one cell, and then generate all permutations for the remaining cells, using all the remaining values. Special case is when there are no more cells to generate permutations for. In that case, the permutation is finished. There is a variation possible here, where you say that one remaining cell is the special case, but this will be touched upon later. Albeit a lot later.
Now if you want to model this as a computer programs, the current cell and remaing cells can be best modeled as being sequential. So the current cell could be referred to with an index, say idx, while the remaining cells start at idx + 1.
And then there’s still the problem of the current value and the remaing values. How will we model those such that no permutations are generated twice.
Suppose we had a pool of values from which to choose. We could choose one, remove it from the pool and continue our algorithm.
The picture below tries to graphically depict this. The value from idx can be deduced from the cell it is under, with numbering starting from 0.
You can see that idx is equal to 0, and the value 1 has been removed from the pool. Now this model is not very good. If I take a value out, I won’t really know how to take the next value so that all values are eventually picked. And when one permutation is complete, how can we proceed to the next? How should we put the values back?
The basic recursive definition proved to be too vague for implementing the algorithm.
We need to refine our recursive algorithm and our pool data structure to be practically applicable.
So the algorithm, which will be embodied in the function Permutate, becomes :
The pool is a global variable called Pool.
The array Permutation is the placeholder for a permutation. It is a global variable.
The value V for the current invocation frame of the function is a local variable.
Permutate has got one argument : the index idx into the array Permutation for which the current invocation is responsible. So this is also a local variable.
- Do we still have values in Pool?
- Iterate as many times as there are values in Pool
- Pick a value – V – from the front of Pool
- Let Permutation[ idx ] = V
- Remove V from ( the front of ) Pool
- Call Permutate( idx + 1 )
- Insert V at the back of Pool
- Iterate as many times as there are values in Pool
- All cells of Permutation have been filled in
An astute reader may have noticed that we are talking about the front and back of pool. Indeed, in order to make the pool manipulation deterministic, we model it as a queue. This way we can make sure that we have shifted through all values of the pool when setting the current value at idx.
But wait a minute, the statement about the queue and shifting through all values sure looks to be correct, but looks can be deceiving.
We still have a huge logical gap in our current algorithm, one which we will need to close in order to prove that the algorithm works. One major condition for this to work, is that the recursive call to a child-permutate does not alter the state of the pool. Only when this is the case, the parent’s loop shifts through all values in the pool. Putting all values of the pool at Permutation[ idx ] was the main task of the parent, so it is critical that the pool remains unchanged as seen from the parent’s viewpoint.
Auwch. This is not so nice, because as we can see, the parent-permutate does alter the pool, and since the child-permutate is the same code as the parent, it will probably also alter the pool.
However, altering the state of the pool is not really a problem, as long as after the child returns, the pool is restored to the same state as the parent left it in, before he called the child.
In simpler terms, the kid can do whatever he wants in with the pool, as long as it is unchanged every time dad comes to check.
Now this is in fact the case. This algorithm will always be able to rely on the fact that the pool is unchanged over a child-permutate call. Proof of this will have to wait to a later version of the algorithm.
Entry filed under: Command Line.