Editing Permutation (section)

====Generation with minimal changes====
{{main|Steinhaus–Johnson–Trotter algorithm|Heap's algorithm}}
An alternative to the above algorithm, the [[Steinhaus–Johnson–Trotter algorithm]], generates an ordering on all the permutations of a given sequence with the property that any two consecutive permutations in its output differ by swapping two adjacent values. This ordering on the permutations was known to 17th-century English bell ringers, among whom it was known as "plain changes". One advantage of this method is that the small amount of change from one permutation to the next allows the method to be implemented in constant time per permutation. The same can also easily generate the subset of even permutations, again in constant time per permutation, by skipping every other output permutation.{{sfn|Knuth|2005|pp=1–26}}

An alternative to Steinhaus–Johnson–Trotter is [[Heap's algorithm]],<ref>{{cite journal|last=Heap|first=B. R.|title=Permutations by Interchanges|journal=The Computer Journal|year=1963|volume=6|issue=3|pages=293–298|doi=10.1093/comjnl/6.3.293|doi-access=free}}</ref> said by [[Robert Sedgewick (computer scientist)|Robert Sedgewick]] in 1977 to be the fastest algorithm of generating permutations in applications.<ref name=sedegewick1977/>

The following figure shows the output of all three aforementioned algorithms for generating all permutations of length <math>n=4</math>, and of six additional algorithms described in the literature.
[[File:Permutation generation algorithms10.svg|thumb|center|upright=2.2|Ordering of all permutations of length <math>n=4</math> generated by different algorithms. The permutations are color-coded, where {{legend-inline|red|1}}, {{legend-inline|yellow|2}}, {{legend-inline|green|3}}, {{legend-inline|blue|4}}.<ref>{{cite web|url=http://combos.org/perm|title=Generate permutations|last1=Mütze|first1=Torsten|last2=Sawada|first2=Joe|last3=Williams|first3=Aaron|website=Combinatorial Object Server|access-date=May 29, 2019}}</ref>]]

# Lexicographic ordering;
# [[Steinhaus–Johnson–Trotter algorithm]];
# [[Heap's algorithm]];
# Ehrlich's star-transposition algorithm:{{sfn|Knuth|2005|pp=1–26}} in each step, the first entry of the permutation is exchanged with a later entry;
# Zaks' prefix reversal algorithm:<ref name="Zaks_1984">{{cite journal|last=Zaks|first=S.|title=A new algorithm for generation of permutations|journal=[[BIT Numerical Mathematics]]|year=1984|volume=24|issue=2|pages=196–204|doi=10.1007/BF01937486|s2cid=30234652}}</ref> in each step, a prefix of the current permutation is reversed to obtain the next permutation;
# Sawada-Williams' algorithm:<ref>{{cite conference |title=A Hamilton path for the sigma-tau problem |last1=Sawada |first1=Joe |last2=Williams |first2=Aaron |date=2018 |publisher=[[Society for Industrial and Applied Mathematics]] (SIAM) | book-title=Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018 |pages=568–575 |location=New Orleans, Louisiana |doi=10.1137/1.9781611975031.37|doi-access=free }}</ref> each permutation differs from the previous one either by a cyclic left-shift by one position, or an exchange of the first two entries;
# Corbett's algorithm:<ref name="Corbett_1992">{{cite journal|last=Corbett|first=P. F.|title=Rotator graphs: An efficient topology for point-to-point multiprocessor networks|journal=IEEE Transactions on Parallel and Distributed Systems|year=1992|volume=3|issue=5|pages=622–626|doi=10.1109/71.159045}}</ref> each permutation differs from the previous one by a cyclic left-shift of some prefix by one position;
# Single-track ordering:<ref name="Arndt_2011">{{cite book |author-last=Arndt |author-first=Jörg|title=Matters Computational. Ideas, Algorithms, Source Code| date=2011| publisher=[[Springer Science+Business Media|Springer]]| doi=10.1007/978-3-642-14764-7|isbn=978-3-642-14763-0}}</ref> each column is a cyclic shift of the other columns;
# Single-track Gray code:<ref name="Arndt_2011"/> each column is a cyclic shift of the other columns, plus any two consecutive permutations differ only in one or two transpositions.
# Nested swaps generating algorithm in steps connected to the nested subgroups <math>S_k\subset S_{k+1}</math>. Each permutation is obtained from the previous by a transposition multiplication to the left. Algorithm is connected to the [[Factorial_number_system]] of the index.