(algorithm)
Definition: Generate permutations by transposing one pair of elements at a time.
Also known as Steinhaus-Johnson-Trotter.
Generalization (I am a kind of ...)
permutation.
See also Fisher-Yates shuffle, Gray code.
Author: PEB
Hale F. Trotter, Perm (Algorithm 115), CACM, 5(8):434-435, August 1962. Available at http://doi.acm.org/10.1145/368637.368660
Selmer M. Johnson, Generation of Permutations by Adjacent Transposition, Mathematics of Computation, 17(83):282-285, July 1963. Available at http://www.jstor.org/sici?sici=0025-5718(196307)17:83<282:GOPBAT>2.0.CO;2-E or http://www.jstor.org/action/showArticle?doi=10.2307/2003846
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 14 August 2008.
HTML page formatted Tue Dec 6 16:16:32 2011.
Cite this as:
Paul E. Black, "Johnson-Trotter", in
Dictionary of Algorithms and Data
Structures [online], Paul E. Black, ed.,
U.S. National Institute of
Standards and Technology. 14 August 2008. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/johnsonTrotter.html
