Thursday, May 01, 2008

Generating all permutations: a non-recursive algorithm

A natural idea for generating all permutations of n elements is to write a recursive algorithm with O(n!) time complexity. The algorithm used in C++ STL function next_permutation is a more efficient solution --- it generates all unique permutations non-recursively and moreover in lexicographic order. The algorithm is given by the great computer scientist Donald Knuth in his book The Art of Computer Programming, Volume 4, Fascicle 2: Generating All Tuples and Permutations. Here is his Draft of Section Generating All Permutations.


awhan said...

this comment may be regarded as spam.

are there any algorithms that can deterministically generate knuth shuffles of a list so that no two corresponding items in resulting random shuffles are identical.
two items are corresponding if they belong to different lists but have the same positional index.

Sven Forstmann said...

I couldnt open the document, but here also a non-recursive version which is quite fast - perhaps the same?

std::string default = "12345";

int perm=1, digits=default.size();
for (int i=1;i<=digits;perm*=i++);
for (int a=0;a0; b--)
int index = (a/div)%b;
printf("%c", avail[index] );
avail.erase(index,1) ;

Its also lexigraphically correct.

(c) Sven Forstmann