What is the best algorithm for finding a $g \in S_n$ which $a^g=b$ for given $a, b \in S_n$

Question

What is the best algorithm for finding a $g \in S_n$ which $a^g=b$ for given $a, b \in S_n$, where $S_n$ is a symmetric group and $a$ and $b$ have same cycle type?

Question 2: Is there any command in GAP that can find such $g$?

Answer 1

Suppose $a=\begin{pmatrix} a_1 & a_2 & a_3 & \ldots a_k\end{pmatrix}$ and $b=\begin{pmatrix} b_1 & b_2 & b_3 & \ldots b_k\end{pmatrix}$, then \begin{align*} gag^{-1} & =g\begin{pmatrix} a_1 & a_2 & a_3 & \ldots a_k\end{pmatrix}g^{-1}\\ & =\begin{pmatrix} g(a_1) & g(a_2) & g(a_3) & \ldots g(a_k)\end{pmatrix} \end{align*} So if you want $$\begin{pmatrix} b_1 & b_2 & b_3 & \ldots b_k\end{pmatrix}= \begin{pmatrix} g(a_1) & g(a_2) & g(a_3) & \ldots g(a_k)\end{pmatrix}$$ then all you need to do is use the permutation $g$ which sends $a_i \to b_i$. You can extend this argument when $a$ and $b$ are not just cycles but product of disjoint cycles.

Answer 2

Answering the 2nd question, the GAP command is RepresentativeAction. For example:

gap> G:=SymmetricGroup(10);
Sym( [ 1 .. 10 ] )
gap> x:=(1,2,3)(7,5,4,9)(6,10);
(1,2,3)(4,9,7,5)(6,10)
gap> y:=(10,9,8)(7,6,5,4)(3,2);
(2,3)(4,7,6,5)(8,10,9)
gap> t:=RepresentativeAction(G,x,y);
(1,8)(2,10,3,9,7,6)
gap> x^t=y;
true

RepresentativeAction works for other actions as well, please see the GAP manual here for further details.