Conjugate permutations

Two permutations are conjugate IFF they have the same cycle structure.

So if we calculate the conjugate of
a=(1 2 3)(4 5) and
b=(3 5),
then we know that the conjugate has the same cycle structure as a. Let's find out:
a^b=(3 5)((1 2 3)(4 5))(3 5)
1 2 3 4 5
1 2 5 4 3 : (3 5) applied
2 5 1 3 4 : (1 2 3)(4 5) applied
2 5 4 3 1 : (3 5) applied
In cycles: (1 2 5)(3 4)

There is a smarter way to get at this result. Permute the cycle structure of a with b:
(1 2 3)(4 5)
(1 2 5)(4 3) = (1 2 5)(3 4).

Using this method we can simply find the conjugating permutation of a and b.
For example
a=(1 2 3)(4 5 6) and
b=(1 3 5)(2 4 6).
Since a and b have the same cycle structure there must be a permutation c such that
a=c b c^-1.
1 2 3 4 5 6 : cycle a as permutation
1 3 5 2 4 6 : cycle b as permutation
We get from a to b by applying cycle
(2 3 5 4) which must be c.
Let's verify.

1 2 3 4 5 6
1 3 5 2 4 6 : apply c
3 5 1 4 6 2 : apply b
3 4 5 6 1 2: apply c^-1 = (2 4 5 3)
In cycles:(1 3 5)(2 4 6) = b.