GAP project: Why Steinhaus' algorithm works

The argument is by mathematical induction.

1. First, note that Steinhaus' algortithm works for $n=2, n=3$.

2. Write down all the elements of $S_{n-1}$ as a list using Steinhaus' algorithm (the induction hypthesis the each differs by a suitable transposition is assumed for this list). We represent each element in the $2\times (n-1)$ array notation. In our list, we simply record the $2^{nd}$ row in the list. ie, as an $(n-1)$-tuple. There are $(n-1)!$ elements in this list.

3. For the $1^{st}$ $(n-1)$-tuple, write an $n$ at the end, for the $2^{nd}$ $(n-1)$-tuple, write an $n$ at the beginning, for the $3^{rd}$ $(n-1)$-tuple, write an $n$ at the end, for the $4^{th}$ $(n-1)$-tuple, write an n at the beginning, and so on. Note we have a sequence of $(n-1)!$ $n$-tuples.

4. Suppose the $i^{th}$ $n$-tuple is $(n,a_1,a_2,...,a_{n-1})$. First, act on this by the transposition $(n,a_1)$, then by the transposition $(n,a_2)$, then by $(n,a_3)$, ..., by $(n,a_n)$. The result of the last one is $(a_1,a_2,...,a_{n-1},n)$. Suppose the $j^{th}$ $n$-tuple is $(b_1,b_2,...,b_{n-1},n)$. (Note that by the induction hypothesis, $(a_1,a_2,...,a_{n-1},n)$ and $(b_1,b_2,...,b_{n-1},n)$ ``differ'' only by a suitable transposition, in $S_{n-1}$.) First, act on this by the transposition $(b_1,n)$,then by the transposition $(b_2,n)$, then by $(b_3,n)$, ..., by $(b_n,n)$. The result of the last one is $(n,b_1,b_2,...,b_{n-1})$.

5. Note that all these (for $i,j$ ranging over even or odd integers from $1$ to $n-1$), the resulting $n!$ $n$-tuples are distinct. This yields a listing of $S_n$ as desired.

Exercise 5.19.16   Program this algorithm in GAP.