Determining whether or not a subset of $S_n$ generates $S_n$ I have a certain family of subsets of $S_n$, and I'd like to know which subsets in this family generate $S_n$. What techniques exist for solving this type of problem?
Are there any known results on necessary or sufficient conditions for a subset of $S_n$ to generate $S_n$? Anything on calculating the order of the subgroup generated by a subset?
 A: Let $X$ be a subset of $S_n$. I suppose that the size of $X$ is small compared to the order of $S_n$. In order to quickly check whether $X$ generates $S_n$ I would do the following: For $k=1,2,3\dots$ check whether the group generated by $X$ is $k$-fold transitive. That is a cheap test: Let $\Gamma$ be the graph whose vertices are the $k$-tuples of distinct elements from $\{1,2,\dots,n\}$. Connect two vertices by an edge if an element from $X$ moves one vertex to the other one. Then the group generated by $X$ is $k$-transitive if and only if $\Gamma$ is connected, which is algorithmically easy and cheap to test.
If $X$ passes the test up to $k=6$, then you know that the generated group is $A_n$ or $S_n$, because there are no other $6$-transitive groups. Deciding between these two cases is a matter of checking the signum of the elements from $X$.
In most degrees $n$, there are no $2$-transitive groups besides $A_n$ or $S_n$, so of course you can stop with $k=2$.
Remark 1 (addressing Derek Holt's comment): Indeed, the number of $6$-tuples gets unmanageably large quickly. Instead of $k$-tuples, one can work with $k$-sets. By Kantor's 1972 paper on $k$-homogeneous groups, a $k$-homogeneous group where $k\ge5$ is $k$-transitive. So except for $n=24$ we have to look at $5$-sets at worst. Of course, certainly there are much more efficient methods available.
Remark 2 (addressing Denis Chaperon de Lauzières' comment): Right, while the algorithm is cheap, the proof of its correctness isn't. The OP didn't tell whether he wants to check many small degree cases (say $n\le30$), or some high degree cases. In the former case, one of course does not need the classification of the finite simple groups in order to classify the highly transitive permutation groups. 
A: One method that often works is the following: A primitive group, which contains a $p$-cycle for a prime $p<n-2$ is $A_n$ or $S_n$. If a permutation $\pi$ contains a cycle of length $p$, and no other cycle of length divisible by $p$, then some power of $\pi$ is a $p$-cycle, and the proportion of permutations having this property tends to 1. So if you have information on the cycle structure of your permutations, and are a little bit lucky, then generation of $S_n$ is the same as generation of a primitive group. From an algorithmic point of view primitivity is not a good property, but often imprimitivity can be ruled out by simple ad hoc arguments.
