Steinhaus–Johnson–Trotter algorithm
Equivalently, this algorithm finds a Hamiltonian cycle in the permutohedron, a polytope whose vertices represent permutations and whose edges represent swaps.
This method was known already to 17th-century English change ringers, and Robert Sedgewick calls it "perhaps the most prominent permutation enumeration algorithm".
[1] 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 generated permutations may be sped up by taking advantage of the similarity between consecutive permutations.
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.
The Steinhaus–Johnson–Trotter algorithm follows this structure: the sequence of permutations it generates consists 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.
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.
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.
[4] Trotter gives an alternative implementation of an iterative algorithm for the same sequence, in lightly commented ALGOL 60 notation.
[6] A subsequent improvement by Shimon Even provides an improvement to the running time of the algorithm by storing additional information for each element in the permutation: its position, and a direction (positive, negative, or zero) in which it is currently moving (essentially, this is the same information computed using the parity of the permutation in Johnson's version of the algorithm).
fraction of all of the swaps performed by the algorithm, the average time per permutation generated is also constant, even though a small number of permutations will take a larger amount of time.
[1] A more complex loopless version of the same procedure suitable for functional programming allows it to be performed in constant time per permutation in every case; however, the modifications needed to eliminate loops from the procedure make it slower in practice.
items may be represented geometrically by a permutohedron, the polytope formed from the convex hull of
-dimensional polytope; for example, the permutohedron on four items is a three-dimensional polyhedron, the truncated octahedron.
Thus, each two consecutive permutations in the sequence generated by the Steinhaus–Johnson–Trotter algorithm correspond in this way to two vertices that form the endpoints of an edge in the permutohedron, and the whole sequence of permutations describes a Hamiltonian path in the permutohedron, a path that passes through each vertex exactly once.
is the larger of the two inverted values), and then interpreting these sequences as numbers in the factorial number system, that is, the mixed radix system with radix sequence
Consecutive permutations in the sequence generated by the Steinhaus–Johnson–Trotter algorithm have numbers of inversions that differ by one, forming a Gray code for the factorial number system.
In this generalized sense, the Steinhaus–Johnson–Trotter algorithm generates a Gray code for the permutations themselves.
These so-called "plain changes" or "plain hunt" were known by circa 1621 for four bells,[12] and the general method has been traced to an unpublished 1653 manuscript by Peter Mundy.
[6] A 1677 book by Fabian Stedman lists the solutions for up to six bells.
[13] More recently, change ringers have abided by a rule that no bell may stay in the same position for three consecutive permutations; this rule is violated by the plain changes, so other strategies that swap multiple bells per change have been devised.
[14] The algorithm is named after Hugo Steinhaus, Selmer M. Johnson and Hale F. Trotter.
Johnson and Trotter rediscovered the algorithm independently of each other in the early 1960s.
[15] A 1958 book by Steinhaus, translated into English in 1964, describes a related impossible puzzle of generating all permutations by a system of particles, each moving at constant speed along a line and swapping positions when one particle overtakes another.
[16] A 1976 paper by Hu and Bien credited Steinhaus with formulating the algorithmic problem of generating all permutations,[17] and by 1989 his book had been (incorrectly) credited as one of the original publications of the algorithm.
