Definition: Generate permutations by swapping one adjacent pair of elements at a time.
Also known as Steinhaus-Johnson-Trotter, Trotter-Johnson.
Generalization (I am a kind of ...)
See also Fisher-Yates shuffle, Gray code, unranking.
Hale F. Trotter, Perm (Algorithm 115), CACM, 5(8):434-435, August 1962.
Selmer M. Johnson, Generation of Permutations by Adjacent Transposition, Mathematics of Computation, 17(83):282-285, July 1963.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 27 October 2022.
HTML page formatted Thu Oct 27 16:27:49 2022.
Cite this as:
Paul E. Black, "Johnson-Trotter", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 27 October 2022. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/johnsonTrotter.html