"Natural" generating sets for symmetric groups The symmetric group on $n$ letters has 
many sets of generators. Some of them are more natural than others, eg the
set $(i,i+1)$ of adjacent transpositions (natural with respect to the type A Weyl group), the set of all shuffles (permutations corresponding to "card-shuffles", ie $\sigma(1),\sigma(2),\dots,$ contains at most two increasing subsequences) perhaps also sets consisting of conjugacy
classes (preferably of signature $-1$ in order to avoid a stupid mistake).
Which other sets of generators of symmetric groups occur in a natural way?
 A: Here's an example: One transposition, and one cycle of length n.
A: Another answer from a combinatorial point of view: the set of all transpositions is a generating set for $S_n$. Obviously this is a huge overkill. But a nice thing about including all transpositions is now your generating set is closed under conjugation. In fact, this generating set is used to define the so-called absolute order or reflection order (which applies more generally to any Coxeter group); the absolute order has as its Hasse diagram the Cayley graph with respect to the transpositions as generating set. Absolute order comes up for instance in Coxeter-Catalan combinatorics, a currently popular topic.
A: I wrote a handout on generating sets for symmetric and alternating groups for an algebra course.  It's available at http://www.math.uconn.edu/~kconrad/blurbs/grouptheory/genset.pdf. 
The table at the end of Section 1 lists several choices of generating sets for $S_n$ and $A_n$.
A: I am not exactly sure what you looking for.  As you know, two random permutations generate $S_n$ or $A_n$ with probability $\to 1$ as $n\to \infty$.  However, if you are looking for generating sets that came up in my work, here a a couple:
1) $a = (12)(34)\cdots$, $b= (23)(45)\cdots$, $c=(12)$.  The generating set $\{a,b,c\}$ comes up in a number of problems and even has a name $(2,2\times 2)$ generating set (three involutions two of which commute).  See here for many refs to $(2,2\times 2)$ generating sets. 
2) $s_i = (1,i)$, $i=2\ldots n$.  These are called "star transpositions" and have a number of interesting combinatorial properties.  See here (pref-f. 2b) how they come up in Knuth ACP.  
A: (apologies for the shameless self-promotion)
The book "Combinatorics of Genome Rearrangements" surveys a lot of these generating sets, with a focus on the symmetric and hyperoctahedral groups as far as permutations are concerned. 
Those sets are "natural" in the sense that they reflect genetic mutations. They are not covered in full mathematical depth, but hopefully you can get a few interesting references out of the survey.
A: The action of the symmetric group on the $2$-sets $\{a,b\}$ with $a \ne b$ is primitive. Hence, the point stabilizer of $\{1,2\}$, i.e., the subgroup $H = \{ g \in \mathcal S_n \mid \{1,2\}^g = \{1,2\} \}$, is maximal. Observe that $H$ is generated by the full symmetric group on $\{3,\ldots, n\}$ and the single transposition that exchanges $1$ and $2$.
So, taking any $g \notin H$ and a generating set for $H$ gives a set of generators for the full symmetric group on $\{1,\ldots,n\}$.
With this observation, it follows that if you take any generating set of the symmetric group on $\{3,\ldots,n\}$, $(1~2)$ and any $g \notin G$, for example $(2~3)$, will generate the symmetric group on $\{1,\ldots,n\}$. For example, the adjacent transpositions $(j~j+1)$ have this form and inductively many other generating sets could be constructed.
A: Since you ask about generating by conjugacy classes, it might be worth remarking that $S_{n} = \langle C \rangle$ for any conjugacy class $C$ consisting of odd permutations. By the simplicity of $A_{n}$ for $n \geq 5$, it suffices to check $n \leq 4$, and only the case $n = 4$ and $C$ the conjugacy class of $4$-cycles requires any effort.
A: You can take any tree $T$ on $[n]$ and the set of transpositions $(i,j)$ for $\{i,j\}$ an edge of $T$ will give a (minimal) generating set for $S_n$. This obviously includes the "usual" generating set of adjacent transposition, as well as the "star transpositions" mentioned by Igor Pak, but also many more examples. In general these generating sets are pretty similar to the usual adjacent transpositions, but have their own interesting combinatorics too. In particular, I believe there's a version of the Vandermonde determinant/bialternant definition of Schur functions that depends on this choice of tree $T$ (due to Alexander Postnikov), but I can't remember the exact details at the moment.
