expressing permutations in terms of generators Suppose I have $G < S_n,$ with generators $g_1, \dots, g_k,$ and I have some $g\in G.$ I want to write $g$ as a word in the generators. How hard is this, computationally? And is there a simple algorithm someone can point me to? I assume Gap and Magma have this built in...
 A: In general the problem is very difficult. There has been quite some work on the diameter of the Cayleygraph of $S_n$, the best results being due to Helfgott-Seress for the general case, and Helfgott-Seress-Zuk for the random case. However, as far as I know these proofs are non-constructive in the sense that they only show the existence of a word of small length, but do not give an algorithm to find this word. 
One approach that sometimes works is to generate short words in the given generators, until you find a word you understand so well that the representation problem becomes trivial. For example, suppose you can find an element which contains a single 2-cycle and no other cycle of even length. Taking powers you get an explicit description of a transposition. Then you construct a 2-transitive subset, and get a representation for any transposition. Finally write the element $g$ as a product of transpositions. 
Bratus and Pak (J. Symbolic Comput. 29 (2000), 33-57) used this approach to give a fast randomized algorithm to find an isomorphism between a black box group and $S_n$. I used it to give an algorithm which for almost all $\pi, \sigma$ finds in polynomial running time a word of length $O(n^3\log n)$ representing any given $g$ ( Combinatorica 32 (2012), 309–323). 
