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 7.2.1.2: Generating All Permutations.
Thursday, May 01, 2008
Subscribe to:
Post Comments (Atom)
Posts
2 comments:
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.
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--)
{
div/=b;
int index = (a/div)%b;
printf("%c", avail[index] );
avail.erase(index,1) ;
}
printf("\n");
}
printf("permutations:%d\n",perm);
Its also lexigraphically correct.
(c) Sven Forstmann
Post a Comment