Generating Permutations with Recursion: Ord-Smith’s Algorithm

[This page is auto-generated; please prefer to read the article’s PDF Form.]

Ord-Smith’s Algorithm

R. Sedgewick in [1] has attributed this algorithm to R. J. Ord-Smith [5]. This algorithm generates the permutations in Lexicographical Order. (Article [6] discussed the deﬁnition of this order, some of its properties, and a non-recursive algorithm to generate permutations in this order.)

#define REVERSE(s1, e1) { \
  int s2 = s1;            \
  int e2 = e1;            \
                          \
  while(s2 < e2)          \
  {                       \
    SWAP(s2, e2);         \
    s2++;                 \
    e2--;                 \
  }                       \
}

void ordsmith(int s)
{
  int i;

  if(s == N-1)
  {
    print();
    return;
  }

  for(i = 0; i < N-s; i++)
  {
    /* Setup Block */
    if(i > 0)
    {
      REVERSE(s+1, N-1);
      SWAP(s, s+i);
    }

    ordsmith(s+1);
  }
}

For generating permutations in lexicographical order, the initial call ordsmith(0) must be done with array a sorted in increasing order.

Let us denote by predicates I(s) and D(s) (for any s) the fact that subarray a[s : N − 1] is in increasing and decreasing order respectively. The algorithm works by enforcing the following speciﬁcation P upon method ordsmith(): if ordsmith(s) is called with I(s) true, then D(s) must hold upon its return.

Note that speciﬁcation P holds trivially for s = N − 1. Now suppose, for some other s, it holds for s + 1. Consider the invocation ordsmith(s) and assume that I(s) holds at its beginning. After its iteration of i = 0, it is clear that D(s + 1) must hold (since the call ordsmith(s + 1) holds P). We claim that at the end of each iteration, D(s + 1) holds. This is because, any iteration with i > 0 which begins with D(s + 1) holding performs:

(a) reversal of a[s + 1 : N − 1] resulting in I(s + 1) holding,
(b) swap which still maintains I(s + 1) (see below),
(c) call to ordsmith(s + 1) which would leave D(s + 1) holding again.

While making the recursive call, the algorithm places at index s the elements of set B (subarray a[s : N − 1]) in increasing order. For i = 0 iteration, we already have the smallest element at index s (since I(s) holds). For all later iterations, the swap picks the next larger element for placing at index s. Since I(s + 1) holds after the reversal, such larger element is easily located by the swap at index s + i. This swap won’t alter the increasing order of a[s + 1 : N − 1], because what replaces the element at index s + i is the element just smaller than it.

It is this placing of increasingly larger elements at index s, which gives the generated permutations the lexicographical order.

We now come back to the claim about D(s + 1). Since D(s + 1) holds at the end of each iteration and the last iteration would place the largest element of a[s : N − 1] at index s, so the loop must terminate with a[s : N − 1] in decreasing order. That is, D(s) must hold upon the method’s return.

Thus, by Mathematical Induction, speciﬁcation P must hold for method ordsmith(s) for all s.

It is interesting to note that this method, though giving a lexicographical result, does not perform any comparison among elements or inspection of their values. These are needed only for the initial sorting of array a. Since this method is thus a pure structural one, it must generate all permutations of a whatever be its initial order. Though, the order of such permutations will be based on the initial order of a, not the lexicographical order of its elements.

References

[1] R. Sedgewick. Permutation Generation Methods. ACM Comput. Surv., Vol 9 (2) (1977), 137–164.

[2] C. T. Fike. A Permutation Generation Method. Comput. J., Vol 18 (1) (1975), 21–22.

[3] B. R. Heap. Permutations by Interchanges. Comput. J., Vol 6 (3) (1963), 293–294.
https://academic.oup.com/comjnl/article/6/3/293/360213.

[4] D. E. Knuth. The Art of Computer Programming, Vol 4A, First Edition. Addison-Wesley (2011).

[5] R. J. Ord-Smith. Algorithm 323: Generation of Permutations in Lexicographic Order. Commun. ACM, Vol 11 (2) (1968), 117.

[6] Nitin Verma. Generating Permutations Lexicographically.
https://mathsanew.com/articles/generating_permutations.pdf.