Johnson-Trotter Algorithm
Listing All Permutations

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:

(1) 1 2 and 2 1.

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

(2) 3 1 2, 1 3 2, 1 2 3 and 3 2 1, 2 3 1, 2 1 3.

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

4 3 1 2, 3 4 1 2, 3 1 4 2, 3 1 2 4.

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

(*) N a b ... z
a N b ... z
a b N ... z
...
a b ... N z
a b ... z 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.

The algorithm requires one more definition: a directed integer is said to be mobile if it is greater than its immediate neighbor in the direction it is looking at.

The Johnson-Trotter algorithm can now be described in five lines:


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

If you try the algorithm by hand or study the sequence of the permutations produced by the applet, you cannot fail to observe that the largest integer N first travels leftwards, lingers there just for one step that flips its direction and also changes a shorter permutation, so that the integer may now travel rightwards, where again at the end it skips a step that changes its direction and the underlying (N-1)-permutation, and so on. The process continues until a strange permutation

<2 <1 3> 4> ... N>

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.

This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at https://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet.

What if applet does not run?

Thus the algorithm generates a circular sequence of permutations and satisfies a (strong) minimal-change requirement. This feature of 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

  • Transpositions
  • Groups of Permutations
  • Sliders
  • Puzzles on graphs
  • Equation in Permutations

    |Contact| |Front page| |Contents| |Algebra| |Activities|

    Copyright © 1996-2018 Alexander Bogomolny

    • 71851996