## A simple and fast permutation generator (2)

*February 14, 2008 at 9:04 pm* *
Leave a comment *

In this installment I will give the basic implementation of the algorithm in C++.

I have purposely kept the algorithm as simple as possible, so no OO or fancy generic programming techniques. Yes I do know that style of Kung-Fu as well but for now I want you to concentrate on the moon, not the finger.

The variable names are the same as the ones in the pseudo-code in the previous article. There is one extra variable, **TheSize**, which is needed to bootstrap the algorithm. It is not functionally required, in the core algorithm it only participates within assert statements.

These assert statements check the invariant relations that should hold at various points in the code.

#include <vector> #include <queue> #include <assert.h> const size_t TheSize = 5 ; std::vector<size_t> Permutation( TheSize ) ; std::queue<size_t> Pool ; void Permutate( const size_t idx ) { assert( idx <= TheSize ) ; assert( TheSize == Permutation.size() ) ; assert( Permutation.size() - idx == Pool.size() ) ; if( Pool.empty() == false ) { assert( idx < TheSize ) ; for( size_t i = 0 ; i != Pool.size() ; ++i ) { const size_t V = Pool.front() ; Pool.pop() ; Permutation[ idx ] = V ; Permutate( idx + 1 ) ; Pool.push( V ) ; } } else { assert( idx == TheSize ) ; printf( "[ %d", Permutation[ 0 ] ) ; for( size_t i = 1 ; i < Permutation.size() ; ++i ) { printf( ",%d", Permutation[ i ] ) ; } printf( " ]\n" ) ; } } int main() { // set up the pool of possible values for( size_t i = 0 ; i < Permutation.size() ; ++i ) { Pool.push( i ) ; } // start the recursion Permutate( 0 ) ; return 0; }

The algorithm above works. Absolutely. There is nothing wrong with it, it is simple to understand and reasonably fast. With reasonably I mean that it could be suited for non-performance critical applications. However, we can still improve this algorithm and speed it up.

Although later versions of the algorithm will be faster, they will all have in common that there is a lower bound to the runtime that is proportional to N!, where N is the size of the Permutation.

What I mean by this is that the algorithm’s runtime will be proportional to something more than N!. Let’s call it X(N!), where X(N!) > N!. What X(N!) exactly is I haven’t analyzed yet. Mainly because I’m not very good at it.

Proportional to N! is known in computer science as being of order O(N!), also called the factorial order.

If you look at this list, you can see that the factorial order is quite bad. It is even worse than the dreaded exponential order, which scientists try avoid if practical computability is an issue.

However, this will not spoil our fun. Yes we will run into computer resource problems sooner than a binary search, but we can sure generate some nice permutations in the meantime.

*Note : after some further quick analysis I have noticed that the runtime is upper-bounded by ( N – 3 )N!.
So (N – 3)N! > X(N!). Now how close exactly this upper bound is to X(N!), I don’t know yet.*

Entry filed under: Command Line.

Trackback this post | Subscribe to the comments via RSS Feed