An algorithm to list all the permutations

In Martin Gardner's Scientific American article [Gar1] an algorithm is mentioned which lists all the permutations of $\{1,2,...,n\}$. This algorithm gives the fastest known method of listing all permutations of $\{1,2,...,n\}$. Rediscovered many times since, the procedure is due originally to the Polish mathematician Hugo Steinhaus (January 1887-February 1972), a student of David Hilbert at Göttingen, did important work on orthogonal series, probability theory, real functions and their applications.

We shall denote each permutation by the second row in its $2\times n$ array notation. For example, in the case $n=2$:

$$\begin{array}{cc} 1& 2\\ 2&1 \end{array}$$

are the permutations.

To see the case $n=3$, the idea is to

(a) write down each row $n=3$ times each as follows:

$$\begin{array}{cc} 1& 2\\ 1& 2\\ 1& 2\\ 2& 1\\ 2& 1\\ 2& 1 \end{array}$$

(b) ``weave" in a $3$ as follows

$$\begin{array}{ccc} 1& 2&3\\ 1& 3&2\\ 3&1& 2\\ 3&2& 1\\ 2&3& 1\\ 2& 1&3 \end{array}$$

In case $n=4$, the idea is to

(a) write down each row $n=4$ times each as follows:

$$\begin{array}{ccc} 1& 2&3\\ 1& 2&3\\ 1& 2&3\\ 1& 2&3\\ 1... ...1\\ 2&3& 1\\ 2& 1&3\\ 2& 1&3\\ 2& 1&3\\ 2& 1&3 \end{array}$$

(b) now ``weave" a 4 in:

$$\begin{array}{cccc} 1& 2&3&4\\ 1& 2&4&3\\ 1&4& 2&3\\ 4&1&... ...& 1\\ 4&2& 1&3\\ 2&4& 1&3\\ 2& 1&4&3\\ 2& 1&3&4 \end{array}$$

In general, we have the following

Theorem 4.5.1 (Steinhaus)   There is a sequence of (not necessarily distinct) 2-cycles, $(a_1,b_1)$,...,$(a_N,b_N)$, where $N=n!-1$, such that each non-trivial permutation $f$ of $\{1,2,...,n\}$ may be expressed in the form

$$f=\prod_{i=1}^k(a_i,b_i),$$

for some $k$, $1\leq k\leq N$. Furthermore, these products (for $k=1,2,...,N$) are all distinct.

In other words, each permutation can be written as a product of (not necessarily disjoint) 2-cycles^4.1.

Example 4.5.2  

Let us consider the result of Steinhaus' algorithm in the case of $S_3$. Recall the output from of the algorithm:

$$\begin{array}{ccc} 1& 2&3\\ 1& 3&2\\ 3&1& 2\\ 3&2& 1\\ 2&3& 1\\ 2& 1&3 \end{array}$$

In disjoint cycle notation,

$$\begin{array}{c} \ [1,2,3]=(1)=g_1, \ \ \ \ [1,3,2]=(2,3)=g... ...=(1,3)g_4=g_5, \ \ \ \ [2,1,3]=(1,2)=(2,3)g_6=g_6. \end{array}$$

Note that every element $g\in S_3$ can be written in the form of a product of the simple transpositions $(1,2)$ and $(2,3)$.

Exercise 4.5.3   Prove Theorem 4.5.1. (Hint: Use Exercise 4.4.15.)