# 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 . This algorithm gives the fastest known method of listing all permutations of . 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 array notation. For example, in the case :

are the permutations.

To see the case , the idea is to

(a) write down each row times each as follows:

(b) weave" in a as follows

In case , the idea is to

(a) write down each row times each as follows:

(b) now weave" a 4 in:

In general, we have the following

Theorem 4.5.1 (Steinhaus)   There is a sequence of (not necessarily distinct) 2-cycles, ,..., , where , such that each non-trivial permutation of may be expressed in the form

for some , . Furthermore, these products (for ) are all distinct.

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

Example 4.5.2

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

In disjoint cycle notation,

Note that every element can be written in the form of a product of the simple transpositions and .

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

david joyner 2008-04-20