Conjugate permutations A permutation of size n is a reordering of the first n positive integers.  (meaning each integer appears once and exactly once).  Permutations can be treated like functions that change the order of a list of items of size n.  For example

(4 1 2 3) ["a", "b", "c", "d"] = ["d", "a", "b", "c"]


Thus permutations can be composed like functions.

(4 1 2 3)(2 1 3 4) = (4 2 1 3)


This brings about a lot of interesting properties.   Today we are focusing on conjugacy.  Permutations y and x (both of size n) are conjugates iff there are permutations g and g-1 (also of size n) such that

x = gyg-1

and gg-1 is equal to the identity permutation (the first n numbers in proper order).

Your task is to take two permutations of the same size via standard input methods and decide whether they are conjugates.  You should output one of two consistent values, one if they are conjugates and the other if they are not.

This is code-golf so answers will be scored in bytes with fewer bytes being better.

There are lots of theorems about conjugate permutations that are at your disposal, so good luck and happy golfing.

You may take input as an ordered container of values (either 1-n or 0-n) representing the permutation like above, or as a function that takes a ordered container and performs the permutation.  If you choose to take function you should take it as an argument rather than have it at a predefined name.

Test Cases

(1) (1) -&gt; True
(1 2) (2 1) -&gt; False
(2 1) (2 1) -&gt; True
(4 1 3 2) (4 2 1 3) -&gt; True
(3 2 1 4) (4 3 2 1) -&gt; False 
(2 1 3 4 5 7 6) (1 3 2 5 4 6 7) -&gt; True
Python 2, 87 bytes



f=lambda P,k:k&lt;1or len({sum([x==eval('L['*k+'x'+']'*k)for x in L])for L in P})&amp;f(P,k-1)


Try it online!

Takes input with P as a pair of both permutations and k their length. Outputs 1 for conjugates and 0 not.

This uses the result:


  Two permutations x and y are conjugate exactly if their k-th powers xk and yk have an equal number of fixed points for every k from 0 to n.


Two conjugate permutations satisfy this because their k-th powers are also conjugate, and conjugacy preserves the count of fixed points. 

It's less obvious that any two non-conjugate permutations always differ. In particular, conjugacy is determined by the sorted list of cycle lengths, and these can be recovered from the counts of fixed points. One way to show this is with linear algebra, though it might be overkill. 

Let X be the permutation matrix for x. Then, the number of fixed points of xk is Tr(Xk). These traces are the power sum symmetric polynomials of the eigenvalues of Xk with multiplicity. These polynomials for k from 0 to n let us recover the corresponding elementary symmetric polynomials of these eigenvalues, and therefore the characteristic polynomial and so the eigenvalues themselves. 

Since these eigenvalues are roots of unity corresponding to the cycles of x, from these we can recover the cycle sizes and their multiplicities. So, our "signature" identifies the permutation up to conjugation.