Composition of permutation to generate all permutations

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)$.

(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.