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... ...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&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... ...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.)