Johnson–Trotter Adjacent Permutations
Walk through permutations with one adjacent swap per step and track parity.
By Riano · Published · Updated · Report a correction
Theory: Johnson-Trotter Algorithm
The Johnson-Trotter algorithm, also known as the Steinhaus-Johnson-Trotter algorithm, generates all permutations of a given length by swapping adjacent elements. By associating each element with a direction (left or right), the algorithm systematically determines the next mobile element to swap, producing every permutation exactly once and tracking parity.
Worked Example
Let's generate the next permutation for size n=3, starting at rank 0. We initialize the permutation as 1, 2, 3 with all directions pointing left (-1). A mobile element is one that is larger than the element it points to. At rank 0, the elements and directions are:
Permutation: [1, 2, 3] Directions: [-1, -1, -1]
The mobile elements are 2 (points to 1) and 3 (points to 2). The largest mobile element is 3. We swap 3 with the adjacent element it points to (2). After swapping, we reverse the direction of all elements larger than 3 (none).
New Permutation: [1, 3, 2] New Directions: [-1, -1, -1]
This gives us the permutation at rank 1. The total permutations for size 3 is 3! = 6.
Experiment
You can interact with the algorithm directly to observe how the permutations are generated step-by-step.
See Johnson-Trotter Adjacent Permutations for the interactive model.
- Set the Size control to 3.
- Set the Rank control to 3.
- Observe the resulting permutation "3,2,1" and its computed rank. Note the trace showing previous steps.
- Change the Size control to 4 and Rank to 23 to view the terminal permutation.
Limitations
The algorithm's time complexity for generating all permutations is O(n!), which makes it impractical for large values of n. Since the number of permutations grows factorially, generating and storing the full sequence requires significant computational resources and memory, restricting its direct use to small permutation sizes.
References
The algorithm is a classic combinatorial generation technique. Detailed analysis and its implementation variations can be found in standard algorithmic literature. See the National Institute of Standards and Technology (NIST) Dictionary of Algorithms and Data Structures for more details:
Experience it interactively
Adjust parameters, observe in real time, and build deep intuition with Riano’s interactive Johnson–Trotter Adjacent Permutations module.
Try Johnson–Trotter Adjacent Permutations on Riano →