Conjugate permutations

Question

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) -> True
(1 2) (2 1) -> False
(2 1) (2 1) -> True
(4 1 3 2) (4 2 1 3) -> True
(3 2 1 4) (4 3 2 1) -> False 
(2 1 3 4 5 7 6) (1 3 2 5 4 6 7) -> True

Answer 1

Python 2, 87 bytes

f=lambda P,k:k<1or len({sum([x==eval('L['*k+'x'+']'*k)for x in L])for L in P})&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 x^k and y^k 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 x^k is Tr(X^k). These traces are the power sum symmetric polynomials of the eigenvalues of X^k 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.

Answer 2

J, 25 bytes 23 bytes 16 bytes

miles' tacit solution :

-:&([:/:~#&>)&C.

OP's explicit solution :

c=:4 :'-://:~"1#&>C.&>x;y'   

This checks whether permutations x and y have the same cycle type, using the built-in C. function to produce cycle representations.

   4 1 3 2   c   4 2 1 3
1
   3 2 1 4   c   4 3 2 1
0
   2 1 3 4 5 7 6   c   1 3 2 5 4 6 7
1

Answer 3

MATL, 20 19 17 16 bytes

xY@!"&G@)@b)X=va

Input: two column vectors (using ; as separator). Output: 1 if conjugate, 0 if not.

Try it online! Or verify all test cases.

Explanation

No theorems about permutations used (out of sheer ignorance); just brute force and these two facts:

• For two permutations p and q, the composition pq is equivalent to using p to index the elements of q.

• The condition x = gyg⁻¹ is equivalent to xg = gy.

Commented code:

x      % Implicitly input first permutation, x. Delete it. Gets copied into clipboard G
Y@     % Implicitly input second permutation, y. Push a matrix with all permutations
       % of its elements, each permutation on a different row. So each matrix row is
       % a permutation of [1 2 ...n], where n is the size of y
!      % Transpose. Now each permutation is a column
"      % For each column
  &G   %   Push x, then y
  @    %   Push current column. This is a candidate g permutation
  )    %   Reference indexing. This gives g composed with y
  @    %   Push current column again
  b    %   Bubble up. Moves x to the top of the stack
  )    %   Reference indexing. This gives x composed with g
  X=   %   Are they equal as vectors? Gives true or false
  v    %   Concatenate stack so far. The stack contains the latest true/false result
       %   and possibly the accumulated result from previous iterations
  a    %   Any: gives true if any element is true. This is the "accumulating" function
       % Implicit end. Implicit display

Answer 4

Jelly, 11 bytes

Œ!©Ụ€ịị"®⁸e

Try it online!

How it works

Œ!©Ụ€ịị"®⁸e  Main link. Left argument: x. Right argument: y

Œ!©          Take all permutations g of x. Copy the result to the register.
   Ụ€        Grade up each; sort the indices of each permutation g by their
             corresponding values. For permutations of [1, ..., n], grading up
             essentially computes the inverse, g⁻¹.
     ị       Let each g⁻¹ index into y, computing g⁻¹y.
      ị"®    Let the results index into the corresponding g, computing g⁻¹yg.
         ⁸e  Test if x occurs in the result.

Answer 5

Wolfram Language (Mathematica), 44 bytes

Equal@@(PermutationCycles[#,Sort[0#]&]&/@#)&

Try it online!

---

Wolfram Language (Mathematica), 44 bytes

x_±y_:=Or@@(#[[x]]==y[[#]]&/@Permutations@x)

Using CP-1252 encoding, where ± is one byte.

Try it online!

Answer 6

Husk, 9 bytes

¤¦ṠmöLU¡!

Returns 1 for conjugate and 0 for non-conjugate. Try it online!

Explanation

The conjugacy class of a permutation P of L = [1,2,..,n] is determined by the multiset containing the least period of each number in L under P. When P is taken in list format, I can replace L with P and get the same multiset. The program computes the corresponding multiset for each input and checks if one is a sub-multiset of the other. Since they have the same number of elements, this is equivalent to being the same multiset.

¤¦ṠmöLU¡!  Implicit inputs: two lists of integers.
¤          Apply one function to both and combine with another function.
  ṠmöLU¡!  First function. Argument: a list P.
  Ṡm       Map this function over P:
       ¡!  iterate indexing into P,
      U    take longest prefix with unique elements,
    öL     take its length.
 ¦         Combining function: is the first list a subset of the other, counting multiplicities?

Answer 7

Perl, 61 58 57 bytes

Includes +2 for ap

Give 0-based permutations as 2 lines on STDIN

perl -ap '$_=[@1]~~[@1=map{-grep$_-$G[$i++%@G],@F=@G[@F]}@G=@F,0]'
3 0 2 1
3 1 0 2
^D

Algorithm is a minor variation on the one in xnor's solution

This older version of the code hits a perl bug and dumps core for several inputs on my latest perl 5.26.1, but it works on an older perl 5.16.3.

@{$.}=map{-grep$_==$F[$i++%@F],@G=@F[@G]}@G=@F,0}{$_=@1~~@2

It's possibly yet another instance of my old perlgolf enemy, the fact that perl doesn't properly refcount its stack.

Answer 8

JavaScript (ES6), 66 64 bytes

(a,b,g=a=>b+a.map(h=(e,i)=>e-i&&1+h(a[e],i)).sort())=>g(a)==g(b)

If I've read the other answers correctly, the problem is equivalent to counting the periods of all the elements and checking that the two lists have the same number of each period. Edit: Saved 1 byte thanks to @Arnauld by calculating one less than the period. Saved another byte thanks to @Arnauld by abusing JavaScript's weird coercion rules to compare the arrays. Another byte could be saved by currying but I don't like curry unless it's chicken tikka masala.