Composition of permutation to generate all permutations 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
 A: 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)$.
A: 
(Disclaimer: I'm writing a somewhat detailed answer, since I noticed this came from SO (and the vocabulary in which the question was formulated). Apologies if it's too long-winded for some.)

If I understand correctly, you have a set S of size n, and you
want to look at the set of all possible permutations P(S) of that set.¹
That P(S) is the symmetric group of order n, usually noted $S_n$. You want to
find a (minimal) generating set of $S_n$.
A generating set of $S_n$ is the set of all transpositions $σ_{i,j}$, for 1 ≤
i,j ≤ n, where $σ_{i,j}$ is the permutation that swaps i and j and leaves
all the other elements unchanged ².
To prove that, you want to show that any permutation can be written as a
"product" (composition) of transpositions. You'll find numerous proofs of that around, let me just say
the gist of it is to proceed by induction on n. Then, given a permutation
p of (n+1) elements, you find a product of transpositions q such that (q ∘
p) (n+1) = (n+1) : then (q∘p) is a permutation of n elements, which by
induction hypothesis can be written as a product of transpositions, and
from that, you can write p itself as a product of transpositions.
That generating set is not minimal: for example, you easily can reduce it to
adjacent transpositions (those transpositions of the form (i,i+1), for 1 ≤ i < n), and still have
a generating set.
Nonetheless, this allows us to notice that to prove a set of permutations
Π is a generating set of $S_n$, it is enough to prove that any adjacent
transposition can be written as a product of permutations in Π.
Let us now take a cycle of maximal length, say (1,2,3,...,n), and a single
adjacent transposition, say (1,2). You'll notice that for any 0 ≤ i <
(n-1)³:
$(1,2,3,...,n)^i(1,2)(1,2,3,...,n)^{-i}$ = (i+1,i+2)
This is the same reasoning we have applied in the link above to show
transpositions can be expressed as a product of adjacent transpositions:
you "shift" all elements using the cycle, apply your transposition, and
then "de-shift" everything.
So, all adjacent transpositions, and therefore all permutations, can be
expressed as a product of a cycle of maximal length and a single adjacent
transposition. I'll leave showing that generating set is minimal as an
exercise.
¹: You'll notice the contents of S are irrelevant, so that we can
denote the elements of S as {1,...,n}, representing the actual elements by
their indexation.
²: In cycle notation, this is also noted (i,j). We'll keep using cycle
notation henceforth.
³: Here, the exponentiation denotes the iterated composition: $p^i$ means
applying i times permutation p.
A: If I understand you correctly, you are looking for elements $\sigma_1, \dots, \sigma_m$ of the symmetric group $S_n$ on $n$ elements such that the sequence
$\sigma_1$, $\sigma_1\circ\sigma_2$, $\sigma_1\circ\sigma_2\circ\sigma_3, \dots, \sigma_1\circ\dots\circ\sigma_m$,
$\sigma_1\circ\dots\circ\sigma_m\circ\sigma_1$, $\sigma_1\circ\dots\circ\sigma_m\circ\sigma_1\circ\sigma_2, \dots, \sigma_1\circ\dots\circ\sigma_m\circ\sigma_1\circ\dots\circ\sigma_m$, $\sigma_1\circ\dots\circ\sigma_m\circ\sigma_1\circ\dots\circ\sigma_m\circ\sigma_1$, $\sigma_1\circ\dots\circ\sigma_m\circ\sigma_1\circ\dots\circ\sigma_m\circ\sigma_1\circ\sigma_2, \dots$ lists every element of $S_n$ exactly once.
Defining $\tau := \sigma_1\circ\dots\circ\sigma_m$ this list can be written as $\tau^0\circ\sigma_1, \dots, \tau^0\circ\sigma_1\circ\dots\circ\sigma_{m-1}$, $\tau^1\circ\sigma_1, \dots, \tau^1\circ\sigma_1\circ\dots\circ\sigma_{m-1}$, $\tau^2\circ\sigma_1, \dots, \tau^2\circ\sigma_1\circ\dots\circ\sigma_{m-1}, \dots$.
Written like this, you see that if $\tau$ has the order $k$ (also called period), the sequence repeats itself after $\dots, \tau^{k-1}\circ\sigma_1\circ\dots\circ\sigma_{m-1}, \tau^k$. So if you pick an element $\tau$ whose order is maximal in $S_n$, you will get $m$ minimal, as you always have
$$m = \frac{|S_n|}{k} = \frac{n!}{k}.$$
Now pick elements $\tau_1, \dots, \tau_m$ from the different right cosets of the (cyclic) group $\langle \tau \rangle$ generated by $\tau$, where without loss of generality you may take $\tau_m = \tau$. Then define $\sigma_1 := \tau_1$ and $\sigma_i := \tau_{i-1}^{-1}\circ\tau_i$ for $i = 2,\dots, m$.
It is then not to hard to prove that this sequence $\sigma_1, \dots, \sigma_m$ fulfills your conditions and is as short as possible if the order of $\tau$ is chosen maximal among the elements of $S_n$. (If you want to know this order, ask another question ;-)).
