Efficient Algorithm for finding left (or right) Transversal in a Group I'm wondering if anyone knows an algorithm to find a left or right transversal in a group efficiently. The definition is you are given a subgroup $H$ of a group $G$, and you want to find a representative of each coset of $H$ in $G$.
Recall the coset test: $x, y \in G$ are in the same coset iff $x^{-1}y \in H$. This yields a trivial $O(|G|)$ algorithm. Simply test each element of $G$ until you find $|H : G|$ unique representatives.
I'm wondering if there is a more efficient way to do this, preferably deterministically. Also, if finding a base or strongly generating set is necessary beforehand, the cost of such should be included in the efficiency of the algorithm.
I am interested in such an algorithm for any arbitrary group, but if a special algorithm exists when $G = S_n$ and $H$ is a permutation group, possibly $S_k$ for some $k < n$, I'd be happy to learn of this as well.
I would also appreciate any references to textbooks or papers that might help solve this problem.
Thanks!

A general reference on algorithms in group theory is the book "Handbook of Computational group Theory" by Holt, Eick and O'Brien.
Algorithms for finding transversals of subgroups of permutation groups are described in Section 4.6.7. This does require a base and strong generating set but, for a subgroup of large index, finding the BSGS will typically be quicker than finding the transversal. The complexity is mainly determined by the size of the output, which depends on the index.
A method for subgroups of solvable groups defined by power-conjugate presentations is described in Lemma 8.33.
