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;
}
void AddItem()
{
// Form a string from Value[0], Value[1], ... Value[N-1].
// At this point, this array contains one complete permutation.
// The string is added to the list box for display.
// The function as such has nothing to do with the algorithms.
}
Try this algorithm by hand to make sure you understand how it works.
Lexicographic order and finding the next permutation:
Permutation f precedes a permutation g in the lexicographic (alphabetic) order iff for the minimum value of k such that f(k) g(k), we have f(k) < g(k). Starting with the identical permutation f(i) = i for all i, the second algorithm generates sequentially permutations in the lexicographic order. The algorithm is described in [Dijkstra], p71.
private void getNext()
{
int i = N - 1;
while (Value[i-1] >= Value[i]) i = i-1;
int j = N;
while (Value[j-1] <= Value[i-1]) j = j-1;
swap(i-1, j-1); // swap values at positions (i-1) and (j-1)
i++; j = N;
while (i < j)
{
swap(i-1, j-1);
i++;
j--;
}
}