Generate permutations

Generate all permutations of the set $\{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.

LexColexZaksWellsHeapLips10Lips16SJTEhrDerSiTSiTGCSWCorb

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.

Download source code

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

References