The Combinatorial Object Server

Size $n$ of ground set | (max. 20) |

Algorithm | |

Output format | |

Output
numbering
graphics

A permutation of an $n$-element set of objects is a linear ordering of those objects, i.e., some object is placed in the first position, another in the second position, etc.
For simplicity, we think of a permutation as a bijection on the set $[n]:=\{1,2,\ldots,n\}$.
Such a bijection $\pi:[n]\rightarrow[n]$ can be represented in many different ways.
We use one-line notation $\pi=(\pi(1),\pi(2),\ldots,\pi(n))$.
For example, all permutations of $[3]=\{1,2,3\}$ are $123, 132, 213, 231, 312, 321$.

The following figure illustrates the output of all eleven algorithms running on this website for generating all permutations of $[4]=\{1,2,3,4\}$ where 1=red, 2=yellow, 3=green, and 4=blue.

Lex | Colex | Zaks | Heap | SJT | Ehr | Der | SiT | SiTGC | SW | Corb |

The first nine algorithms are part of Jörg Arndt's FXT library. The algorithm for lexicographic ordering is explained as Algorithm L in Knuth's book [Section 7.2.1.2, Knu11]. The algorithm for generating permutations by reversing prefixes was discovered by Zaks [Zak84]. The minimal-change order algorithm transposes only two elements in each step and is described in Heap's paper [Hea63]. The algorithm for generating permutations by adjacent transpositions is also known as Steinhaus-Johnson-Trotter algorithm [Ste64, Joh63, Tro62] or `plain changes'. It is described as Algorithm P in Knuth's book [Knu11]. The algorithm using star transpositions always swaps the first element of the permutation with some other element. It was discovered by Gideon Ehrlich and is described as Algorithm E in Knuth's book [Knu11]. In the derangement order no two successive permutations have any element at the same position. This algorithm is described in Savage's survey [Sav97]. In a single track ordering of permutations, each column in the list of permutations is a cyclic shift of the first column. In a single track Gray code ordering, in addition to the previous property, any two consecutive permutations differ only in at most two transpositions (only a single transposition for odd $n$). These two algorithms are described in Arndt's documentation of the FXT library [Arn10]. The single track property of these two orderings can be seen very nicely by arranging the permutations circularly, yielding a wheel where any two circular tracks differ only by rotation (left: single track ordering, right: single track Gray code ordering).

The second to last algorithm in each step either swaps the first two entries of the permutation, or rotates the entire permutation to the left. Whether such a listing exists for all $n$ is posed as an open problem in Knuth's book [Problem 71 in Section 7.2.1.2, Knu11], and the solution is described in the paper by Sawada and Williams [SW18]. The last algorithm in each step rotates a prefix of the permutation one position to the left, and it is described in a paper by Corbett [Cor92].

The number of permutations of an $n$-element set is $n!$, which is OEIS A000142.

- [Arn10] J. Arndt. Matters Computational - Ideas, Algorithms, Source Code [The fxtbook]. www.jjj.de, 2010.
- [Cor92] P. F. Corbett. Rotator graphs: An efficient topology for point-to-point multiprocessor networks. IEEE Transactions on Parallel and Distributed Systems, 3:622–626, 1992.
- [Hea63] B. R. Heap. Permutations by interchanges. The Computer Journal, 6(3):293–298, 1963.
- [Joh63] S. Johnson. Generation of permutations by adjacent transposition. Math. Comp., 17:282–285, 1963.
- [Knu11] D. E. Knuth. The Art of Computer Programming. Vol. 4A. Combinatorial Algorithms. Part 1. Addison-Wesley, Upper Saddle River, NJ, 2011.
- [Sav97] C. Savage. A survey of combinatorial Gray codes. SIAM Rev., 39(4):605–629, 1997.
- [Ste64] H. Steinhaus. One hundred problems in elementary mathematics. Basic Books, Inc., Publishers, New York, 1964. With a foreword by Martin Gardner.
- [SW18] J. Sawada and A. Williams. A Hamilton path for the sigma-tau problem. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, pages 568–575, 2018.
- [Tro62] H. Trotter. Algorithm 115: Perm. Commun. ACM, 5(8):434–435, Aug 1962.
- [Zak84] S. Zaks. A new algorithm for generation of permutations. BIT, 24(2):196–204, 1984.