The –Johnson–Steinhaus–Johnson–Trotter algorithm or Johnson–Trotter algorithm, also called plain changes, is an algorithm named after Hugo Steinhaus, Selmer M. Johnson and Hale F. Trotter that generates all of the permutations of elements. Each permutation in the sequence that it generates differs from the previous permutation by swapping two adjacent elements of the sequence. Equivalently, this algorithm finds a Hamiltonian cycle in the permutohedron.
This method was known already to 17th-century English change ringers, and calls it "perhaps the most prominent permutation enumeration algorithm". A version of the algorithm can be implemented in such a way that the average time per permutation is constant. As well as being simple and computationally efficient, this algorithm has the advantage that subsequent computations on the permutations that it generates may be sped up because of the similarity between consecutive permutations that it generates.
Algorithm
The sequence of permutations generated by the Steinhaus–Johnson–Trotter algorithm has a natural recursive structure, that can be generated by a recursive algorithm. However the actual Steinhaus–Johnson–Trotter algorithm does not use recursion, instead computing the same sequence of permutations by a simple iterative method. A later improvement allows it to run in constant average time per permutation.
Recursive structure
The sequence of permutations for a given number can be formed from the sequence of permutations for by placing the number into each possible position in each of the shorter permutations. The Steinhaus–Johnson–Trotter algorithm follows this structure: the sequence of permutations it generates consists of blocks of permutations, so that within each block the permutations agree on the ordering of the numbers from 1 to and differ only in the position of . The blocks themselves are ordered recursively, according to the Steinhaus–Johnson–Trotter algorithm for one less element. Within each block, the positions in which is placed occur either in descending or ascending order, and the blocks alternate between these two orders: the placements of in the first block are in descending order, in the second block they are in ascending order, in the third block they are in descending order, and so on.
Thus, from the single permutation on one element,
one may place the number 2 in each possible position in descending order to form a list of two permutations on two elements,
Then, one may place the number 3 in each of three different positions for these two permutations, in descending order for the first permutation 1 2, and then in ascending order for the permutation 2 1:
The same placement pattern, alternating between descending and ascending placements of , applies for any larger value of . In sequences of permutations with this recursive structure, each permutation differs from the previous one either by the single-position-at-a-time motion of , or by a change of two smaller numbers inherited from the previous sequence of shorter permutations. In either case this difference is just the transposition of two adjacent elements. When the first and final elements of the sequence, also, differ in only two adjacent elements (the positions of the numbers and ), as may be proven by induction.
This sequence may be generated by a recursive algorithm that constructs the sequence of smaller permutations and then performs all possible insertions of the largest number into the recursively-generated sequence. The same ordering of permutations can also be described equivalently as the ordering generated by the following greedy algorithm. Start with the identity permutation . Now repeatedly transpose the largest possible entry with the entry to its left or right, such that in each step, a new permutation is created that has not been encountered in the list of permutations before. For example, in the case the sequence starts with , then flips with its left neighbor to get . From this point, flipping with its right neighbor would yield the initial permutation , so the sequence instead flips with its left neighbor and arrives at , etc. The direction of the transposition (left or right) is always uniquely determined in this algorithm. However, the actual Steinhaus–Johnson–Trotter algorithm does not use recursion, and does not need to keep track of the permutations that it has already encountered. Instead, it computes the same sequence of permutations by a simple iterative method.