Steinhaus–Johnson–Trotter algorithm
The Steinhaus–Johnson–Trotter algorithm, also known as the Johnson–Trotter algorithm, is a classic procedure for systematically generating all permutations of a finite set of n distinct elements through a sequence of exactly n! - 1 adjacent transpositions, where each successive permutation differs from the previous by swapping exactly two neighboring elements.[1] This approach ensures that the permutations form a Hamiltonian path in the Cayley graph of the symmetric group Sn generated by adjacent transpositions, also called the permutohedron graph.[1] The algorithm is particularly efficient, achieving an amortized time complexity of O(1) per permutation after an initial setup, making it suitable for applications requiring exhaustive enumeration without redundant computations.[1]
Named after Polish mathematician Hugo Steinhaus, American mathematician Selmer M. Johnson, and Canadian-American mathematician Hale F. Trotter (d. 2022), the algorithm emerged from independent discoveries in the early 1960s, though its conceptual roots trace back to 17th-century English change ringing practices for producing "plain changes" in bell sequences.[2] Steinhaus outlined the method in his 1963 book One Hundred Problems in Elementary Mathematics, posing it as a combinatorial challenge.[3] Johnson formalized an iterative version using adjacent transpositions in a 1963 paper, emphasizing its utility for computational generation. Trotter independently published a procedural implementation in 1962 as Algorithm 115 in Communications of the ACM, focusing on practical programming aspects.[4] These contributions established it as a foundational technique in combinatorial generation, later analyzed in depth by Robert Sedgewick in his 1977 survey on permutation methods.[1]
At a high level, the algorithm maintains a current permutation and assigns a "direction" (left or right) to each element indicating potential mobility for swapping. It identifies the largest "mobile" element—one that can swap in its assigned direction without violating ordering—and performs the swap, then reverses the directions of all elements larger than the swapped one to prepare for the next iteration.[1] This process continues until all permutations are exhausted, often starting from the identity permutation and ending at its reverse. The method's minimality in changes between consecutive outputs has inspired variants, including loopless implementations and extensions to restricted permutation classes, underscoring its enduring influence in algorithms for Gray codes and exhaustive search.[2]
Fundamentals
Definition and Purpose
The Steinhaus–Johnson–Trotter algorithm is a method for generating all n! permutations of a set of n distinct elements such that each consecutive pair in the sequence differs by exactly one adjacent transposition, producing a complete enumeration where successive permutations are minimally altered. This approach ensures that the algorithm outputs a sequence starting from an initial permutation (typically the identity) and systematically visits every possible arrangement without repetition, relying solely on swaps of neighboring elements.
The primary purpose of the algorithm is to provide an efficient traversal of the symmetric group S_n, forming a Hamiltonian path in the Cayley graph of S_n generated by the set of adjacent transpositions; this graph connects permutations that differ by such a swap, enabling a linear ordering of all n! elements with n! - 1 minimal transitions.[5] Adjacent swaps are specifically utilized because they minimize the structural changes between permutations, which is advantageous in applications requiring incremental modifications, such as computational enumeration tasks or simulations where abrupt rearrangements would be inefficient.[6] Equivalently, this path corresponds to a Hamiltonian route on the permutohedron, the polytope whose vertices represent permutations and edges denote adjacent transpositions.[7]
The algorithm is named after mathematicians Hugo Steinhaus, Selmer M. Johnson, and Hale F. Trotter, who independently described variants in the early 1960s, building on earlier combinatorial insights. It has historical ties to "plain changes" in the practice of change ringing for church bells, where the method allows ringers to produce all possible sequences of bell strikes without repetition or omission, each change involving only adjacent bells.[8]
Key Properties
The Steinhaus–Johnson–Trotter algorithm generates all n! permutations of n elements exactly once, providing a complete enumeration without repetitions or omissions. This completeness arises from its recursive structure, which systematically explores the symmetric group Sn by building upon smaller permutations.
A core property is its minimality, as successive permutations differ solely by an adjacent transposition—swapping two neighboring elements—ensuring that no permutation involves displacements beyond immediate neighbors. This minimal-change succession traces a Hamiltonian path through the graph where vertices are permutations and edges connect those differing by adjacent swaps.
The algorithm's sequence is reversible: traversing backward simply inverts the adjacent swaps, allowing generation in reverse order while preserving the minimal-change property. In its standard form, however, it yields a path rather than a cycle, though modifications can extend it to a Hamiltonian cycle in the permutohedron.[2]
Regarding efficiency, the original implementation incurs O(n) time per permutation, resulting in O(n · n!) total time to produce the full list. Even's speedup, by precomputing directions and positions of mobile elements, achieves amortized O(1) time per permutation, with loopless variants further optimizing to constant amortized time overall.
Equivalently, the algorithm produces a Gray code for permutations, where the order corresponds to a reflective Gray code on their inversion tables: each transition alters precisely one entry in the inversion table by ±1, reflecting the adjacent swap's effect on inversions.[2]
Algorithm Description
Recursive Approach
The Steinhaus–Johnson–Trotter algorithm admits a natural recursive formulation that builds the sequence of all n! permutations of \{1, 2, \dots, n\} from the sequence of (n-1)! permutations of \{1, 2, \dots, n-1\}. This construction proceeds in two blocks of (n-1)! permutations each. The permutations of the smaller set are generated recursively in their Steinhaus–Johnson–Trotter order (or its reverse, depending on parity), and the largest element n is inserted successively into each of the n possible positions around the smaller permutation to produce the extended sequence. For each fixed smaller permutation, n moves unidirectionally through these positions via adjacent transpositions, ensuring that consecutive permutations differ only by swapping n with an adjacent element.[9]
The direction of insertion for n alternates between the two blocks and depends on the parity of n to maintain the property of adjacent transpositions throughout the full sequence. Specifically, if n is odd, the first block uses the forward Steinhaus–Johnson–Trotter order of the n-1 permutations, with n inserted in descending positions (from right end moving left). The second block uses the reverse order of the n-1 permutations, with n inserted in ascending positions (from left end moving right). If n is even, the directions are reversed: ascending in the first block (forward order) and descending in the second (reverse order). This systematic alternation keeps n as the "mobile" element—always able to swap adjacently—until it reaches one end of the current permutation, at which point the recursion on the smaller set advances to the next one, preserving the adjacent-swap property across block boundaries.[9]
A high-level pseudocode outline for this recursive approach is as follows, where the function yields the sequence of permutations (using 0-based indexing for insertion positions 0 to n-1, where 0 is before the first element and n-1 is after the last):
function SJT(n):
if n == 0:
yield empty list
else:
smaller = list(SJT(n-1)) # Get the full sequence for n-1 (for illustration; inefficient in practice)
if n % 2 == 1: # Odd n
# First block: forward smaller, insert n descending positions (right to left)
for π in smaller:
for pos in range(n-1, -1, -1): # Positions from n-1 down to 0
yield insert(π, n, pos)
# Second block: reverse smaller, insert n ascending positions (left to right)
for π in reversed(smaller):
for pos in range(n): # Positions 0 to n-1
yield insert(π, n, pos)
else: # Even n
# First block: forward smaller, insert n ascending positions
for π in smaller:
for pos in range(n): # Positions 0 to n-1
yield insert(π, n, pos)
# Second block: reverse smaller, insert n descending positions
for π in reversed(smaller):
for pos in range(n-1, -1, -1): # Positions n-1 down to 0
yield insert(π, n, pos)
function SJT(n):
if n == 0:
yield empty list
else:
smaller = list(SJT(n-1)) # Get the full sequence for n-1 (for illustration; inefficient in practice)
if n % 2 == 1: # Odd n
# First block: forward smaller, insert n descending positions (right to left)
for π in smaller:
for pos in range(n-1, -1, -1): # Positions from n-1 down to 0
yield insert(π, n, pos)
# Second block: reverse smaller, insert n ascending positions (left to right)
for π in reversed(smaller):
for pos in range(n): # Positions 0 to n-1
yield insert(π, n, pos)
else: # Even n
# First block: forward smaller, insert n ascending positions
for π in smaller:
for pos in range(n): # Positions 0 to n-1
yield insert(π, n, pos)
# Second block: reverse smaller, insert n descending positions
for π in reversed(smaller):
for pos in range(n-1, -1, -1): # Positions n-1 down to 0
yield insert(π, n, pos)
Here, insert(π, n, pos) returns a new list with n inserted at index pos in π (shifting subsequent elements right). This formulation generates the desired Hamiltonian path on the permutohedron via adjacent transpositions, though practical implementations often favor the original iterative version for efficiency.
Original Iterative Method
The original iterative method for the Steinhaus–Johnson–Trotter algorithm, developed independently by Trotter and Johnson, generates all permutations of n elements through a loop-based procedure that relies on adjacent swaps guided by element directions, ensuring each successive permutation differs by exactly one such swap. This approach avoids recursion by maintaining two arrays: one for the current permutation \pi of the integers $1 to n, and another for the directions d associated with each integer, where d_k indicates whether integer k points left (toward smaller indices) or right (toward larger indices).
The procedure initializes the permutation as the identity \pi = (1, 2, \dots, n) and sets all directions to left, meaning each element k at position i aims to swap with the element at i-1 if possible. It then enters a loop that continues until no mobile elements remain: an element k at position i is mobile if it points left and k > \pi_{i-1} (or right and k > \pi_{i+1}), respecting boundary conditions. In each iteration, the algorithm scans the permutation to identify the largest mobile element k^*, swaps it with its directed neighbor to produce the next permutation, and outputs this new arrangement.
Following the swap, the directions of all elements larger than k^* are reversed. The scan for the largest mobile and the reversal both require O(n) time, making each of the n! steps O(n) overall, for a total time of O(n \cdot n!).
Even's Speedup
In 1973, Shimon Even introduced an optimization to the iterative Steinhaus–Johnson–Trotter algorithm that enhances efficiency by maintaining directional information for each element and a pointer to the current largest mobile element, thereby avoiding exhaustive scans of the permutation array in each step.[10] This technique assigns a direction (left or right) to each element, indicating the orientation of its mobility path in the permutohedron, and uses an index pointer array to track the positions of these elements. After performing an adjacent swap to generate the next permutation, the pointer to the largest mobile element is updated incrementally by examining only the predecessor or successor element based on the swap's direction, rather than rescanning the entire array.[10]
The modified steps involve reversing the directions of all elements larger than the swapped mobile element, which can be done efficiently using the directional arrows to propagate changes along affected paths without full traversal. This is often implemented with a threaded structure implicit in the direction array, ensuring that direction reversals are localized to the elements impacted by the swap. As a result, the algorithm achieves amortized O(1) time per permutation generation, leading to a total time complexity of O(n!) for producing all n! permutations, a significant improvement over the baseline O(n) per step in the original iterative method.[10]
While the worst-case time per permutation remains O(n) due to occasional scans when the mobile element reaches a path endpoint, the average case is constant time because the uniform distribution of permutations ensures these scans are rare and balanced over the full generation cycle.[10]
Examples and Applications
Small-Scale Illustrations
To illustrate the Steinhaus–Johnson–Trotter algorithm, consider the case of n=3 elements labeled 1, 2, and 3. The algorithm generates all 6 permutations in a sequence where each consecutive pair differs by a single adjacent swap, starting from the identity permutation 123. The full sequence is 123 → 213 → 231 → 321 → 312 → 132.[11]
The evolution can be visualized in the following table, showing the permutation at each step, the positions swapped to reach the next (1-based indexing), and the number of inversions (pairs out of natural order), which changes by exactly 1 with each adjacent transposition:
| Step | Permutation | Swap Positions | Inversions |
|---|
| 0 | 123 | 1-2 | 0 |
| 1 | 213 | 2-3 | 1 |
| 2 | 231 | 1-2 | 2 |
| 3 | 321 | 2-3 | 3 |
| 4 | 312 | 1-2 | 2 |
| 5 | 132 | - | 1 |
Practical Uses
The Steinhaus–Johnson–Trotter algorithm finds application in combinatorics for enumerating all permutations of a set, where the property of generating successive permutations via adjacent transpositions facilitates exhaustive search in optimization problems.
In computing applications, its minimal-change property—where each permutation differs from the previous by exactly one adjacent swap—lends itself to graphics and animation tasks requiring smooth transitions between arrangements of elements, such as interpolating configurations in procedural generation or visual simulations of combinatorial structures.[12]
A prominent practical domain is change ringing, the English art of bell ringing, where the algorithm directly composes "plain hunt" methods by generating sequences of bell orders that cover all permutations while ensuring each transition is an adjacent swap, adhering to the tradition's rules for non-repetitive ringing.[8] For instance, on four bells, it produces the full 24 permutations starting and ending in the standard "rounds" order (1-2-3-4), mirroring historical extents rung on church bells.[8] Historical and modern software implementations, such as web-based simulators, employ the algorithm to compose and audition these ringing patterns, aiding ringers in planning complex peals.[13]
Modern extensions of the algorithm include loopless variants that generate each successive permutation in constant worst-case time, enhancing suitability for resource-constrained environments like embedded systems where real-time processing is essential.[14] These versions achieve amortized O(1) time per permutation.[15] Implementations in programming languages such as Python, including coroutine-based generators post-2013, facilitate its use in software libraries for efficient permutation streaming.[16] Compared to recursive backtracking methods, the Steinhaus–Johnson–Trotter algorithm requires no storage of intermediate permutations of smaller sizes and uses constant additional space beyond the current permutation, making it preferable for memory-efficient, on-the-fly generation in large-scale computations.[17]
Mathematical Connections
Permutohedron
The permutohedron associated with the Steinhaus–Johnson–Trotter algorithm is defined as the convex hull in \mathbb{R}^n of the n! points obtained by applying all permutations in the symmetric group S_n to the coordinate vector (1, 2, \dots, n). These points all lie in the affine hyperplane \sum_{i=1}^n x_i = \binom{n+1}{2}, so the permutohedron is an (n-1)-dimensional polytope. Its vertices correspond exactly to the n! permutations of the n elements, and two vertices are joined by an edge if and only if the corresponding permutations differ by an adjacent transposition (i.e., a swap of neighboring positions).
The Steinhaus–Johnson–Trotter algorithm generates a Hamiltonian path on this permutohedron, visiting each of the n! vertices exactly once via a sequence of adjacent transpositions along the edges. This path consists of exactly n! - 1 edges, tracing a route through the entire 1-skeleton of the polytope without revisiting any vertex. The resulting ordering ensures that consecutive permutations in the sequence are adjacent in the permutohedron. The permutohedron is Hamilton laceable for n \geq 4, meaning there exists a Hamiltonian path between any two vertices in different bipartition sets, a property reflected in the SJT path's structure.[2]
For n=3, the permutohedron is a $2-dimensional regular hexagon embedded in \mathbb{R}^3within the planex + y + z = 6. The vertices can be coordinatized as the projections of the permutation points onto this plane (orthogonal to the vector (1,1,1)), yielding positions such as (1,2,3), (1,3,2), (2,1,3), (3,1,2), (2,3,1), and (3,2,1), which form the hexagon's corners in cyclic order. The Steinhaus–Johnson–Trotter path traverses this hexagon sequentially, for example, via the sequence $123 \to 132 \to 312 \to 321 \to 231 \to 213, connecting adjacent vertices without crossings in the embedding.
Key properties of this Hamiltonian path include its role as a Gray code under the inversion metric, where each step changes the total number of inversions by exactly $1$, reflecting the path's movement across inversion levels in the weak Bruhat order realized by the permutohedron. Additionally, the path exhibits no self-intersections within the polytope's geometric embedding, maintaining a non-crossing trajectory that respects the convex structure.
A permutation Gray code is a listing of all permutations of a set such that consecutive permutations differ by a single adjacent transposition, minimizing changes between successive elements in the sequence. In the context of the Steinhaus–Johnson–Trotter algorithm, this property ensures that each step alters only neighboring positions, which is equivalent to changing exactly one inversion in the permutation's inversion table. This minimal alteration makes the sequence particularly useful for applications requiring efficient traversal of the symmetric group S_n.[2]
The Steinhaus–Johnson–Trotter order constructs such a Gray code through a recursive, reflected process on the symmetric group, analogous to the binary reflected Gray code but adapted for combinatorial objects. It leverages the Lehmer code (or equivalently, the inversion table) as a bijective representation of permutations, where each code corresponds to the number of inversions for each position. During generation, the algorithm directs the mobility of elements based on this representation, ensuring that reflections reverse the direction of the largest mobile element to produce the next permutation via an adjacent swap. This reflected structure guarantees a Hamiltonian path in the Cayley graph of S_n generated by adjacent transpositions.[2][18]
Unlike binary Gray codes, which operate on bit strings and change one bit at a time, permutation Gray codes from the Steinhaus–Johnson–Trotter algorithm are tailored to discrete combinatorial structures, with the key distinction that changes are always adjacent to preserve the graph's connectivity. This adjacency ensures no non-local jumps, distinguishing it from other permutation listings like lexicographic order. The algorithm's output forms a path on the permutohedron, the graph where vertices are permutations and edges connect those differing by adjacent swaps.[2][18]
Extensions of this Gray code include bijections to alternative listings, such as those based on other generating sets or restricted permutation classes, facilitating universal generation frameworks.[2][18]
Historical Development
Early Origins
The practice of change ringing emerged in 17th-century England as a method for producing varied sequences of bell tones, with early systematic approaches to generating permutations appearing around 1621 for sets of four bells. These "plain changes" involved producing all 24 possible orderings of the bells through successive adjacent swaps, ensuring smooth transitions in the ringing order without abrupt shifts.[19]
Fabian Stedman formalized these techniques in his 1668 treatise Tintinnalogia, where he described plain changes as swaps between adjacent bells, designating one bell as the "hunt" that progresses through positions while the others exchange places in pairs at the sequence's extremes. For four bells, Stedman outlined 24 changes rung in multiple ways, emphasizing the hunt's upward and downward paths interspersed with extreme swaps to cover all permutations. His 1677 work Campanologia extended this to up to six bells, providing explicit lists of change sequences.[20][21]
In the non-computational setting of bell towers, these swap sequences served to create harmonious musical and acoustic patterns, with Stedman's texts including textual diagrams to guide ringers on the progression of changes and avoid repetitions.[22]
By the 18th century, mathematical interest in permutations grew through Leonhard Euler's studies, which advanced enumeration techniques and combinatorial analysis, such as in his work on derangements and constrained arrangements, though without explicit methods for generating sequences via adjacent transpositions; these efforts provided a theoretical underpinning for the permutation compositions observed in campanology.
The 19th century saw a shift toward puzzle-based explorations of permutations, exemplified by the 15-puzzle invented in 1878, where tiles slide into adjacent spaces, highlighting permutation parity as an invariant that determines solvability for half of all configurations but stopping short of full permutation enumeration.
In 1958, Hugo Steinhaus posed the problem of systematically generating all permutations of a finite set through successive adjacent transpositions in his book 100 Problems in Elementary Mathematics, with the English translation published in 1964.[2] This challenge highlighted the need for an efficient iterative method to traverse the permutation space with minimal changes between consecutive outputs, inspiring subsequent formal solutions.
Independently, H. F. Trotter developed an iterative algorithm for this purpose in 1962, published as Algorithm 115 in Communications of the ACM. Shortly thereafter, Selmer M. Johnson provided a detailed constructive proof and implementation in his 1963 paper "Generation of permutations by adjacent transposition" in Mathematics of Computation, establishing the core procedure of directing and swapping mobile elements to produce the sequence. These works formalized the algorithm, now bearing their names alongside Steinhaus, as a canonical approach to permutation enumeration.
A key refinement came in 1973 with Shimon Even's publication Algorithmic Combinatorics, which introduced a pointer-based speedup to identify the largest mobile element in constant time per permutation, reducing the overall complexity from linear to amortized constant time per step.
Later developments focused on efficiency enhancements, including loopless variants that generate the next permutation in constant time without nested loops, as referenced in Donald E. Knuth's The Art of Computer Programming, Volume 4A (2011 edition).[23] Modern implementations, such as those explored by Aaron Williams in his 2013 work on Gray codes for permutations, emphasize practical coding and extensions to related structures. Post-2020 applications include adaptations for random permutation sampling in quantum circuits, drawing on the algorithm's structure to enable efficient uniform generation for machine learning tasks.[24]
The algorithm's enduring significance is affirmed by its inclusion as a standard method in Knuth's The Art of Computer Programming, Volume 4A (2011), underscoring its role in combinatorial algorithm design.[23]