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.

Exercise 4.5.2   Prove this. (Hint: Use Exercise 4.4.15.)