Johnson–Trotter Adjacent Permutations
Walk through permutations with one adjacent swap per step and track parity.
Free theory articleWalk through permutations with one adjacent swap per step and track parity.
Concept & interpretation
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.
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.