# Generate permutations

Generate all permutations of the set $\{1,2,\ldots,n\}$.
 Size $n$ of ground set (max. 20) Algorithm lexicographic order colexicographic order reversing prefixes (Zaks) transpositions (Wells) transpositions (Heap) transpositions (Lipski 10) transpositions (Lipski 16) adjacent transpositions (Steinhaus-Johnson-Trotter) star transpositions (Ehrlich) derangement order single track single track Gray code prefix swaps and rotations (Sawada-Williams) prefix rotations (Corbett) Output format graphics (≤500 objects) text (≤10000 objects) file (≤100000 objects)
Output  numbering graphics

## Object info

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 $=\{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 $=\{1,2,3,4\}$ where 1=red, 2=yellow, 3=green, and 4=blue.

 Lex Colex Zaks Wells Heap Lips10 Lips16 SJT Ehr Der SiT SiTGC SW Corb

The first twelve 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]. In a transposition ordering, any two consecutive permutations differ in a swap of two entries of the permutation. Such orderings by transpositions were described by Wells [Wel61], Heap [Hea63], and in a more general form by Lipski [Lip79]. Several of Lipski's algorithms are available in the FXT library, and two of them are running on this website (in addition to Wells' and Heap's algorithm, which are special cases of Lipski's; see [Arn10]). All of the Lipski orderings, and in particular the Wells and Heap ordering, have the property that permutations with the same suffix appear consecutively. 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].

Permutations are generalized by multiset permutations and colored permutations, and more algorithms for generating them can be found in those sections.

## Enumeration (OEIS)

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

## References

• [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. Comput. J., 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.
• [Lip79] W. Lipski, Jr. More on permutation generation methods. Computing, 23(4):357–365, 1979.
• [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.
• [Wel61] M. B. Wells. Generation of permutations by transposition. Math. Comp., 15:192–195, 1961.
• [Zak84] S. Zaks. A new algorithm for generation of permutations. BIT, 24(2):196–204, 1984.