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

[New Book: Scalable Permutations]

[QuickPerm] | [EXAMPLE 02] | [EXAMPLE 03] | [EXAMPLE 04] | [MetaPerm]
[Download the Five C++ Examples] | [Permutation Exercises]
[Contact the Author] | [Make a Donation] | [Links]

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


Copyright © 2022 by Phillip Paul Fuchs, all rights reserved. Valid XHTML 1.1 Strict Valid CSS!
Abstracting with credit is permitted...