Algorithms – Composition of Permutation to Generate All Permutations

algorithmspermutations

Looking at permutations I came up with the following question:

Can you find a permutation $S$ of a set of $n$ elements such that by composing this permutation $n!$ times you will describe all the possible permutations of this set.

i.e, all permutation of a given set can be expressed as a composition of this permutation.

But it's not possible:

Proof: (not sure it's the most straightforward proof)

let $S$ be a permutation, it can be decomposed into disjoint cycles. Finding a permutation S that verify the above constraint would mean that the least common multiple of these cycles is n!.

So at least decompose $S$ into one cycle of $n$ elements, one cycle of $n-1$ etc.

But it's impossible since the cycle are disjoints.

Now, may be instead of looking for a single permutation to generate all permutations, I could look at a composition of permutation that will describe all the permutations of a set.

For example, I would like to find $S_1$ and $S_2$ such that $S_1$, $S_1\circ S_2$, $S_1\circ S_2\circ S_1$ etc. describe all the permutations.

With a set of $3$ elements it's pretty easy to find such $S_1$ and $S_2$:

S1 = 1 2 3  //permute first and second element
     2 1 3

S2 = 1 2 3  //permute first and third element
     3 2 1

By composing S1, S1°S2 etc… I get

1 2 3 
2 1 3
3 1 2
1 3 2
2 3 1 
3 2 1

My question is, what is the minimum number of permutations for a set of n element that will describe all the set. Is there an easy way to get these permutations?

Thanks in advance.

EDIT:

thanks for your answers I rephrased the question on another question : Question on permutation

Best Answer

The symmetric group on $n$ symbols is not cyclic when $n>2$ (it's not even abelian). Hence it cannot be generated by a single permutation. However, it can always be generated by two permutations, a transposition $(12)$ and a cycle $(123\ldots n)$.

Related Question