## 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.

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

To be continued…

Entry filed under: Command Line.

Trackback this post | Subscribe to the comments via RSS Feed