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.

Advertisements

Entry filed under: Command Line.

A simple and fast permutation generator (1) A simple and fast permutation generator (3)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Trackback this post  |  Subscribe to the comments via RSS Feed


Recent Posts

Categories


%d bloggers like this: