Generating All Permutations of a Set

Consider a set of $n$ positive integers $A = \{1, 2, ..., n \}$. As we have already noted, the number of $n$-permutations $(x_1, x_2, ..., x_n)$ for this set will be $n!$ which is obtained by selecting one of the $n$ elements in $A$ and placing it in the $x_1$ position; selecting one of the $n - 1$ remaining elements in $A$ and placing it in the $x_2$ position; …; and placing the remaining element in $A$ in the $x_n$ position.

On The Factorial Function page we saw that as $n$ grows, $n!$ rapidly grows, and as a result, it is often not realistic to be able to list all $n!$ permutations of $A$ if $n$. For example, a $10$-element set will have over $3.6$ million $10$-permutations!

Regardless though, it is certainly possible to list all $n!$ $n$-permutations of elements in an $n$-element set, though, we must be careful in listing all of them. We would not want to accidentally list a permutation multiple times and we would not want to miss any permutations either. Fortunately, there's a rather simple algorithm for generating the $n$-permutations of an $n$-element set.

Consider the $3$-element set of positive integers $A = \{1, 2, 3 \}$. For every permutation $(x_1, x_2, x_3)$ where $x_1, x_2, x_3 \in A$ if we delete the $3$ we will obtain a $2$-permutation of the $2$-element set $A \setminus \{ 3 \} = \{1, 2 \}$. For example, consider all of the $3$-permutations of $A$ which there are $3! = 6$ of them listed below.

$(1, 2, 3)$

$(1, 3, 2)$

$(2, 1, 3)$

$(2, 3, 1)$

$(3, 1, 2)$

$(3, 2, 1)$

Now delete the $3$ from each of these $3$-permutations to get $2$-permutations of the set $A \setminus \{ 3 \}$.

$(1, 2)$

$(1, 2)$

$(2, 1)$

$(2, 1)$

$(1, 2)$

$(2, 1)$

Now that the set $A \setminus \{ 3 \} = \{1, 2 \}$ has only $2$ elements and so there are $2! = 2$ permutations of the elements from this set, namely $(1, 2)$ and $(2, 1)$ which appear above. In fact, these $2$-permutations appear $3$ times each. Conversely, given the set $A \setminus \{ 3 \}$, if we take each of the $2!$ $2$-permutations, write them each $3$ times, and then insert the number $3$ exactly once in a distinct position of each $2$-permutation then we obtain what we had to begin with - all $3! = 6$ of the $3$-permutations of elements from $A$.

Theorem 1: If $A = \{ 1, 2, ..., n-1 \}$ and all $(n - 1)!$ many $(n - 1)$-permutations of elements in $A$ are given, then all $n!$-permutations of elements in $A \cup \{ n \}$ can be obtained by writing the each of the $(n - 1)!$ permutations of $A$ down exactly $n$ times and then inserting the number $n$ exactly once in a distinct position of each copy of the $(n - 1)$-permutations then we obtain a list of all $n!$ permutations of $A \setminus \{ n \}$.

• Proof: If we take the $(n - 1)!$ many $(n - 1)$-permutations of elements in $A$ and write them down $n$ times each then there will be $n \cdot (n - 1)! = n!$ many permutations total. Since we place the number $n$ exactly once in each distinct position of each copy of the $(n - 1)$-permutations then each $n$-permutation is unique. Thus we have accounted for all $n!$ many $n$-permutations of the set $A \setminus \{ n \}$. $\blacksquare$

Let's construct all $4!$ permutations using the algorithm presented in Theorem 1. We first start with all $3!$ of the $3$-permutations of the set $\{1, 2, 3 \}$ and write each of these permutations $4$ times to get:

$(1, 2, 3)$	$(1, 2, 3)$	$(1, 2, 3)$	$(1, 2, 3)$
$(1, 3, 2)$	$(1, 3, 2)$	$(1, 3, 2)$	$(1, 3, 2)$
$(2, 1, 3)$	$(2, 1, 3)$	$(2, 1, 3)$	$(2, 1, 3)$
$(2, 3, 1)$	$(2, 3, 1)$	$(2, 3, 1)$	$(2, 3, 1)$
$(3, 1, 2)$	$(3, 1, 2)$	$(3, 1, 2)$	$(3, 1, 2)$
$(3, 2, 1)$	$(3, 2, 1)$	$(3, 2, 1)$	$(3, 2, 1)$

We now place the number $4$ once in all possible positions for each of the permutations above. The table below lists all $4! = 24$ of the $4$-permutations of the set $\{ 1, 2, 3, 4 \}$.

$(4, 1, 2, 3)$	$(1, 4, 2, 3)$	$(1, 2, 4, 3)$	$(1, 2, 3, 4)$
$(4, 1, 3, 2)$	$(1, 4, 3, 2)$	$(1, 3, 4, 2)$	$(1, 3, 2, 4)$
$(4, 2, 1, 3)$	$(2, 4, 1, 3)$	$(2, 1, 4, 3)$	$(2, 1, 3, 4)$
$(4, 2, 3, 1)$	$(2, 4, 3, 1)$	$(2, 3, 4, 1)$	$(2, 3, 1, 4)$
$(4, 3, 1, 2)$	$(3, 4, 1, 2)$	$(3, 1, 4, 2)$	$(3, 1, 2, 4)$
$(4, 3, 2, 1)$	$(3, 4, 2, 1)$	$(3, 2, 4, 1)$	$(3, 2, 1, 4)$