A simple and fast permutation generator (3)

February 14, 2008 at 11:28 pm Leave a comment

OK. Watching TV didn’t really work to keep my mind off the problem of the exact runtime order of the algorithm.
After some fiddling around, I came to the following, albeit recursive, formula for the runtime order :

Let G(N) be number of times in the inner loop-code is executed.
The inner loop code is this part :

const size_t  V = Pool.front() ;
Pool.pop() ;
Permutation[ idx ] = V ;
Permutate( idx + 1 ) ;
Pool.push( V ) ;

It’s this part that does the work, so it will define the time it takes to run the algorithm.

Well as it turns out G(N) = G(N-1)N + N

So, if you know the number of times it takes for N = 3, then you can calculate it for N = 4, etc…
And for N = 1, this number is 1.

How to calculate this number in a non-recursive fashion, I have no idea. It reminds me however of the formula to calculate the number of digits in a Pascal triangle of a certain depth M. This formula is ( M + 1 ) * M / 2. This latter formula resembles the formula for the area of a rectangular triangle in a Cartesian coordinate system with base = M : Area = M*M / 2, which should come as no surprise since a Pascal triangle could be considered a rectangular triangle.

Below you can see a graph of the runtime order with the lower and upper bounds : lower = O(N!), upper = O( NN! ).

In the previous article I stated that O( (N-3)N! ) was an upper bound but in fact any constant c will do to create a formula : (N-c)N! that eventually is an upper bound for the runtime. As soon as N > c, the formula becomes an upper bound. So I made the constant 0, which gives a nicer formula.
The Y-axis is logarithmic.

RunTimeBounds

As you can clearly see, the runtime of the algorithm stays nicely between the stated bounds.

To be continued…

Advertisements

Entry filed under: Command Line.

A simple and fast permutation generator (2) A simple and fast permutation generator (4)

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: