## A simple and fast permutation generator (6)

*February 22, 2008 at 11:55 pm* *
Leave a comment *

It’s been a while since the last permutation generator article. Mainly because of lack of time, but also because I found out about std::next_permutation. I have been looking at that for a while, and although it’s far from simple, it’s somewhat faster than the fastest installment of the recursive algorithm. The speed of std::next_permutation is also lower bound to O(N!) but still faster overall. For generating all the permutations of 11 items, next_permutation’s runtime is about 2/3 of the time taken by the recursive algo.

However, all that won’t stop me from showing you how to make the original algorithm faster. A key component in improving speed was doing away with std::queue, and replacing it with a custom, dedicated and very specific fixed length queue. This queue has got very few methods, and does not offer lots of flexibility. It does not even have a method to get the size. How we manage to write the algorithm without a size method for the queue is something that will be tackled in another future post.

For today, I give you the source code for the fixed size queue. Have fun.

template< size_t ac_nSize > class CFixedSizeQueue { public: CFixedSizeQueue( const size_t ac_FirstValue ) : mv_nFront( 0 ) , mv_nBack ( 0 ) { mv_Array[ mv_nFront ] = ac_FirstValue ; } size_t pop() { const size_t c_Result = mv_Array[ mv_nFront ] ; mv_nFront = mv_nFront < sc_nSize - 1 ? mv_nFront + 1 : 0 ; return c_Result ; } void push( const size_t ac_Value ) { mv_nBack = mv_nBack < sc_nSize - 1 ? mv_nBack + 1 : 0 ; mv_Array[ mv_nBack ] = ac_Value ; } size_t front() const { return mv_Array[ mv_nFront ] ; } private: static const size_t sc_nSize = ac_nSize ; typedef size_t mt_Array[ sc_nSize ] ; size_t mv_nFront ; size_t mv_nBack ; mt_Array mv_Array ; }; CFixedSizeQueue< gc_nSize > Pool( 0 ) ;

A couple of extra notes on this class :

- CFixedSizeQueue demands that there is at least one element in the queue at all times. This requires to pass the first item in the ctor of the queue. Yet another thing that you wouldn’t want in a generic queue.
- The method of clamping the indices, mv_nBack and mv_nFront, to values within the bounds of the array looks kind of slow, with the ternary operator, but it turned out to be faster than either using the modulo operator – % – or than some form of bit masking using the bit-wise and operator – & -.
- Another thing you might have noticed is that the pop method returns the element that is popped. This also save a couple of cycles compared to a separate Pool.front and Pool.pop sequence.
- There is no error or bounds checking whatsoever, nor is there any defense against degenerate use. This class is definitely not liberal in what it accepts. Something that’s quite ok if you know what you are doing, but may not be suited for a library.
- WordPress’s pre-formatted text handling is driving me nuts.

Entry filed under: Command Line.

Trackback this post | Subscribe to the comments via RSS Feed