Definition: Generate permutations by transposing one pair of elements at a time.

Also known as Steinhaus-Johnson-Trotter.

Generalization (I am a kind of ...)

See also Fisher-Yates shuffle, Gray code.

Author: PEB

More information

Hale F. Trotter, Perm (Algorithm 115), CACM, 5(8):434-435, August 1962. Available at
Selmer M. Johnson, Generation of Permutations by Adjacent Transposition, Mathematics of Computation, 17(83):282-285, July 1963. Available at<282:GOPBAT>2.0.CO;2-E or

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 2 March 2015.
HTML page formatted Fri Feb 23 10:06:07 2018.

Cite this as:
Paul E. Black, "Johnson-Trotter", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 2 March 2015. (accessed TODAY) Available from: