These algorithms and descriptions were found at: http://www.cut-the-knot.com/do_you_know/AllPerm.html

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

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

[QuickPerm] | [EXAMPLE 02] | [EXAMPLE 03] | [EXAMPLE 04] | [MetaPerm]

[Download the Five C++ Examples] | [Permutation Exercises]

[Contact the Author] | [Make a Donation] | [Links]

[HOME]

Help keep public education alive! We need your donations, click here to help now...

{top}