Generate permutations

Generate all permutations of the elements $\{1,2,\ldots,n\}$.
Size $n$ of ground set (max. 20)
Algorithm
Output format
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 $[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.

LexColexZaksHeapSJTEhrDerSiTSiTGCSWCorb

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].

Enumeration (OEIS)

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

Download source code

[Zipped C++ source code (GNU GPL)]
[Link to Jörg Arndt's FXT library (GNU GPL)]

References