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


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

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

Copyright © 2024 by Phillip Paul Fuchs, all rights reserved.
Abstracting with credit is permitted...