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