# Johnson-Trotter Algorithm

Listing All Permutations

A permutation of a set is an ordering of all its elements. For example, for the set

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) | 1 2 and 2 1. |

Two elements in each of the permutations in (1) define 3 positions for the 3^{rd} 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 4^{th} element 4. For example, the first permutation there

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

(*) |
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

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

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

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

Copyright © 1996-2018 Alexander Bogomolny