Counting And Listing All Permutations:
Johnson-Trotter Algorithm

A permutation of a set is an ordering of all its elements. For example, for the set {a, b, c, T} we can define two different permutations (but there are more, of course} a, c, T, b and T, c, b, a. If the elements of a set are indexed, then a permutation of indices uniquely determines a permutation of the set's elements. For example, index the elements of the set {a, b, c, T} with numbers 1, 2, 3, 4. Then its two sample permutations above correspond to the two permutations of indices, 1, 3, 4, 2 and 4, 3, 2, 1. It follows that as soon as we know how to get permutations of a set of indices {1 2 3 ... N}, for a given N, we know how to permute any set with N elements.

There are many ways to list all permutations of the given length N. A most natural approach builds permutations of growing length successively starting with the shortest ones. A 1-element set, say {1}, has only one permutation: 1. Moving to the set {1, 2} of two elements, we see that the additional element 2 can be appended to the permutation of {1} in two ways: on the left and on the right. Thus we get two permutations:

Two elements in each of the permutations in (2) define 3 positions for the 3^rd element 3:

Three elements in each of the permutations in (3) define 4 positions to place the 4^th element 4. For example, the first permutation there 3 1 2 leads to 4 permutations:

In general, there are N ways to extend a permutation a b ... z of length N-1 to a permutation of length N:

The method just described is simple and appeals directly to the definition of a permutation. No tricks are involved. It has a drawback, though. You must compute a whole pyramid of permutations shorter than the ones you need. Some may not mind doing that. Some may be curious if there are shortcuts. The Johnson-Trotter algorithm (H. F. Trotter[1962], S. M. Johnson[1963]) offers a clever way to directly generate permutations of the required length without computing shorter permutations.

If you stare for a while at (*), it may occur to you that N - the length of and the largest number in the permutations - travels rightwards from the leftmost available position to the rightmost. Of course, listing the permutations (*) in the reverse order would reverse the direction of the travel as well. To embody the traveling metaphor into action, the Johnson-Trotter algorithm replaces integer as the basic element of the procedure with a structure that maintains an integer and a direction. Call the structure a directed integer, or just an integer if the context is clear. The direction may take on only one of two values, "left" or "right", and can be implemented as a boolean. In the applet below, an integer k directed leftwards appears as <k; directed rightwards, it appears as k>. It's convenient and certainly appropriate to say that a directed integer is looking left- or rightwards depending on the value of the attached field direction.

Initialize the first permutation with <1 <2 ... <n
while there exists a mobile integer
  find the largest mobile integer k
  swap k and the adjacent integer it is looking at
  reverse the direction of all integers larger than k

is reached at which point no mobile integers exist. Note that this permutation is obtained from the initial 1 2 ... N by a single transposition which, in addition, swaps two adjacent elements. In fact, it is a remarkable and a prized feature of the algorithm that any two successive permutations it generates are obtained from each other by a single transposition of adjacent elements.

Thus the algorithm generates a circular sequence of permutations and satisfies a (strong) minimal-change requirement. In that the algorithm is reminiscent of the de Bruijn cycle and the Gray codes.

Reference

1. A. Levitin, Introduction to The Design & Analysis of Algorithms, Addison Wesley, 2003

Permutations

• Various ways to define a permutation
• Counting and listing all permutations
• Counting and listing all permutations: Johnson-Trotter

Groups of Permutations

• Group multiplication of permutations
• Permutations as a Product of Transpositions
• Product of permutations
• Recombining Permutations

Copyright © 1996-2008 Alexander Bogomolny