Recursive and Lexicographic Algorithms

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;
}

{
// Form a string from Value, Value, ... 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--;
}
}
``````

These algorithms and descriptions were found at:  http://www.cut-the-knot.com/do_you_know/AllPerm.html
Send all questions and concerns to the CTK Exchange
Author: Alexander Bogomolny

Reference:
1. E.W.Dijkstra, A Discipline of Programming, Prentice-Hall, 1976