{menu} {mirror}

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
    for (int i = 0; i < N; i++)
      if (Value[i] == 0)

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

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

  1. E.W.Dijkstra, A Discipline of Programming, Prentice-Hall, 1976
  2. R.Sedgewick, Algorithms, Addison-Wesley, 1983