Steinhaus–Johnson–Trotter algorithm
The Steinhaus–Johnson–Trotter algorithm or Johnson–Trotter algorithm, also called plain changes, is an algorithm named after Hugo Steinhaus, Selmer M. Johnson and Hale F. Trotter that generates all of the permutations of elements. Each permutation in the sequence that it generates differs from the previous permutation by swapping two adjacent elements of the sequence. Equivalently, this algorithm finds a Hamiltonian cycle in the permutohedron.
- Abstraction100002137
- Act100030358
- Activity100407535
- Algorithm105847438
- Change107296428
- Event100029378
- Happening107283608
- Procedure101023820
- PsychologicalFeature100023100
- Rule105846932
- software
- Substitution107443761
- Variation107337390
- WikicatCombinatorialAlgorithms
- WikicatPermutations
- YagoPermanentlyLocatedEntity
- Comment
- enThe Steinhaus–Johnson–Trotter algorithm or Johnson–Trotter algorithm, also called plain changes, is an algorithm named after Hugo Steinhaus, Selmer M. Johnson and Hale F. Trotter that generates all of the permutations of elements. Each permutation in the sequence that it generates differs from the previous permutation by swapping two adjacent elements of the sequence. Equivalently, this algorithm finds a Hamiltonian cycle in the permutohedron.
- Depiction
;_Steinhaus%E2%80%93Johnson%E2%80%93Trotter.svg)
- Has abstract
- enThe Steinhaus–Johnson–Trotter algorithm or Johnson–Trotter algorithm, also called plain changes, is an algorithm named after Hugo Steinhaus, Selmer M. Johnson and Hale F. Trotter that generates all of the permutations of elements. Each permutation in the sequence that it generates differs from the previous permutation by swapping two adjacent elements of the sequence. Equivalently, this algorithm finds a Hamiltonian cycle in the permutohedron. This method was known already to 17th-century English change ringers, and calls it "perhaps the most prominent permutation enumeration algorithm". A version of the algorithm can be implemented in such a way that the average time per permutation is constant. As well as being simple and computationally efficient, this algorithm has the advantage that subsequent computations on the permutations that it generates may be sped up because of the similarity between consecutive permutations that it generates.
- Hypernym
- Algorithm
- Is primary topic of
- Steinhaus–Johnson–Trotter algorithm
- Label
- enSteinhaus–Johnson–Trotter algorithm
- Link from a Wikipage to an external page
- ageconsearch.umn.edu/record/272202/files/erasmus129.pdf
- www.cs.utexas.edu/users/EWD/transcriptions/EWD05xx/EWD502.html
- www.cs.utexas.edu/users/EWD/ewd05xx/EWD553.PDF
- www-cs-faculty.stanford.edu/~uno/fasc2b.ps.gz
- Link from a Wikipage to another Wikipage
- ALGOL 60
- Algorithm
- Category:Combinatorial algorithms
- Category:Permutations
- Cayley graph
- Change ringing
- Convex hull
- Fabian Stedman
- Factorial number system
- File:Symmetric group 4; Cayley graph 1,2,6 (3D); Steinhaus–Johnson–Trotter.svg
- File:Symmetric group 4; permutation list; Steinhaus–Johnson–Trotter.svg
- File:Wheel diagram of Steinhaus-Johnson-Trotter algorithm for n=4.svg
- Fisher–Yates shuffle
- Gray code
- Hale F. Trotter
- Hamiltonian cycle
- Hamiltonian path
- Heap's algorithm
- Hugo Steinhaus
- Inverse element
- Inversion (discrete mathematics)
- Iterative method
- Loopless algorithm
- Mixed radix
- Parity of a permutation
- Permutation
- Permutohedron
- Polytope
- Radix
- Recursive algorithm
- Selmer M. Johnson
- Shimon Even
- SIAM Review
- Symmetric group
- Truncated octahedron
- SameAs
- 4ZxhG
- Algoritmo de Steinhaus–Johnson–Trotter
- m.07nm5d
- Q4925248
- Steinhaus-Johnson-Trotter algoritam
- Steinhaus-Johnson-Trotter-Algorithmus
- Շտայնհաուզ-Ջոնսոն-Թրոթթեր ալգորիթմ
- الگوریتم استینهوس-جانسون-تروتر
- ขั้นตอนวิธีของชไตน์เฮาส์ จอห์นสันและทร็อทเทอร์
- 스테인하우스-존슨-트로터 알고리즘
- Subject
- Category:Combinatorial algorithms
- Category:Permutations
- Thumbnail
;_Steinhaus%E2%80%93Johnson%E2%80%93Trotter.svg?width=300)
- WasDerivedFrom
- Steinhaus–Johnson–Trotter algorithm?oldid=1116241633&ns=0
- WikiPageLength
- 20305
- Wikipage page ID
- 2568963
- Wikipage revision ID
- 1116241633
- WikiPageUsesTemplate
- Template:Bi
- Template:Citation
- Template:Harvtxt
- Template:OEIS2C
- Template:Refbegin
- Template:Refend
- Template:Reflist
- Template:Sfnp
