Recursive and Lexicographic Algorithms
These algorithms and descriptions were found at: http://www.cut-the-knot.com/do_you_know/AllPerm.html
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
for (int i = 0; i < N; i++)
if (Value[i] == 0)
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)
Send all questions and concerns to the CTK Exchange
Author: Alexander Bogomolny
- E.W.Dijkstra, A Discipline of Programming, Prentice-Hall, 1976
- R.Sedgewick, Algorithms, Addison-Wesley, 1983