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, 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.


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


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

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

    Copyright © 1996-2018 Alexander Bogomolny

  • 71683142