Wednesday, March 25, 2009

Can anyone make sense of the recursive algorithm?

I was working on this problem:

A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:

012 021 102 120 201 210

What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

and I found this page:

http://www.cut-the-knot.org/do_you_know/AllPerm.shtml

"Recursive algorithm

The recursive algorithm is short and mysterious. It's executed with a call visit(0). Global variable level is initialized to -1 whereas every entry of the array Value is initialized to 0.

void visit(int k)
{
level = level+1; Value[k] = level; // = is assignment

if (level == N) // == is comparison
AddItem(); // to the list box
else
for (int i = 0; i < N; i++)
if (Value[i] == 0)
visit(i);

level = level-1; Value[k] = 0;
}

"

Can anyone make sense of this?

DF

No comments: