Overview
The Steinhaus-Johnson-Trotter Algorithm enumerates permutations in adjacent-transposition order by tracking mobile elements and changing their directions.
ExtendedSource checked
Steinhaus-Johnson-Trotter Algorithm
Generates permutations so adjacent outputs differ by one adjacent swap.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Procedural Generation
- Difficulty
- Intermediate
- Family
- Permutation generation
- Tier
- Extended
- Status
- Verified
- Review
- Source Checked
- Sources
- 3
- Formulas
- 0
- Relationships
- 2
- Code example
- Not ready
- Visualization
- Not ready
- Aliases
- Johnson-Trotter Algorithm, Trotter-Johnson Algorithm, Plain changes
Core Concepts
permutation generationadjacent transpositionmobile elementsminimal-change order
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n!) generated permutations
Average
O(n!) generated permutations
Worst
O(n!) generated permutations
Space
O(n) direction and permutation state plus output storage if materialized
When to Use
- Use when neighboring permutations should differ by a single adjacent swap.
When Not to Use
- Avoid when permutation order is irrelevant and a simpler recursive enumerator is enough.
What It Does
- Assigns a direction to each element.
- Finds the largest mobile element.
- Swaps it with its neighbor and reverses directions of larger elements.
Use Cases
- Permutation enumeration
- Gray-code-like generation
- Combinatorial testing
Inputs
- A finite ordered set of n items.
Outputs
- Every permutation, with adjacent outputs differing by one adjacent transposition.
Pseudocode
- 1.Initialize directions.
- 2.Find the largest mobile element.
- 3.Swap it in its direction.
- 4.Reverse directions of larger elements.
Canonical Example
- Input
- [1, 2, 3]
- Output
- A sequence of six permutations where each consecutive pair differs by an adjacent swap.
- Explanation
- The largest mobile element determines the next adjacent transposition.
Implementation Notes
- A mobile element is larger than the adjacent element in its current direction.
Common Pitfalls
- Forgetting to reverse directions of all elements larger than the moved element.
Interactive Mechanism Walkthrough
Spatial Primitive & Sweep-Line CanvasShow mobile elements, direction arrows, and adjacent swaps between successive permutations.
Step 1 of 4: Initialize directions.
adjacent-transpositionNotes
Steinhaus-Johnson-Trotter generates permutations by adjacent transpositions; procedural-generation is the closest current Atlas category.
Sources (3)
What each reference supports for this entry.
NIST DADS Johnson-Trotter
EncyclopediaDefines Johnson-Trotter as generating permutations by adjacent swaps and records Steinhaus-Johnson-Trotter aliases.
Open sourceJohnson (1963)
PaperSupports the adjacent-transposition permutation-generation method underlying the Johnson-Trotter family.
Open sourceTrotter (1962)
PaperSupports Algorithm 115, PERM, as an early permutation-generation algorithm associated with the Trotter-Johnson naming.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageAlternative toHeap's Algorithm
Steinhaus-Johnson-Trotter and Heap's Algorithm are alternative deterministic permutation-generation methods.
Related Algorithms
Tags
Procedural Generation