17
\$\begingroup\$

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 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
\$\endgroup\$
  • \$\begingroup\$ Can we take input as a function? Can we also take in the size n? \$\endgroup\$ – xnor Feb 16 '18 at 0:34
  • \$\begingroup\$ @xnor Sure on both counts. I'm not sure how the first will help you though. \$\endgroup\$ – Sriotchilism O'Zaic Feb 16 '18 at 0:35
  • \$\begingroup\$ The default function input rules allow the function to be assumed to be predefined, which saves bytes on writing it as an argument, if you allow it. \$\endgroup\$ – xnor Feb 16 '18 at 0:40
  • \$\begingroup\$ @xnor Are we talking about this rule? That is for black box functions which permutations are not. This makes sense because that consensus is designed to allow languages without function pointers/objects to compete whereas here they can because permutations can be represented otherwise. \$\endgroup\$ – Sriotchilism O'Zaic Feb 16 '18 at 0:43
  • \$\begingroup\$ I was, I didn't think of the distinction of them being black-box. So here, the input may be a function, but only as an explicit argument? \$\endgroup\$ – xnor Feb 16 '18 at 0:45
6
\$\begingroup\$

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 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.

\$\endgroup\$
6
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to PPCG and nice first post. I shortened your method to 16 bytes -:&([:/:~#&>)&C. by using a tacit form. Here's a TIO link to try it out. \$\endgroup\$ – miles Feb 16 '18 at 13:47
  • \$\begingroup\$ Thank you. :) I'm still quite a J beginner, and though I seem to easily put it to good use with explicit forms, composing efficient tacit forms still require an excessive lot of thought for me. I'll add your solution. \$\endgroup\$ – Mathias Dolidon Feb 16 '18 at 14:01
  • \$\begingroup\$ PS : don't we count the function assignments' chars as well ? c=: \$\endgroup\$ – Mathias Dolidon Feb 16 '18 at 14:15
  • 1
    \$\begingroup\$ @MathiasDolidon No, by default consensus, we don't count the chars required for assignment, since the function may be used as-is (with parentheses, but we don't count them). \$\endgroup\$ – Erik the Outgolfer Feb 16 '18 at 14:49
  • 1
    \$\begingroup\$ OK ! I've retroactively updated the counts for the explicit solution in the title to take this into account. \$\endgroup\$ – Mathias Dolidon Feb 16 '18 at 15:04
4
\$\begingroup\$

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−1 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
\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ As far as I understand, it's actually y which indexes into each g⁻¹, not the other way around. See the example, (4 1 2 3)(2 1 3 4) = (4 2 1 3). With your approach, it would result in (1 4 2 3) instead, since the second indexes into the first. Taking that into account, I have a 12-byte solution I won't spoil yet. :-) \$\endgroup\$ – Erik the Outgolfer Feb 16 '18 at 11:21
  • \$\begingroup\$ @EriktheOutgolfer Fixed. \$\endgroup\$ – Dennis Feb 16 '18 at 12:38
  • \$\begingroup\$ @Dennis But I didn't come to that conclusion based on the explanation, I arrived to the exact same approach, except that I had something like Œ!©Ụ€⁹ịЀ®ị"⁸e (basically all indexing with reversed arguments), except shorter after I made major modifications. I don't think g⁻¹yg is the same as gyg⁻¹. Also, I think your answer can benefit from those modifications too, but, as I said before, I don't want to ruin the fun yet. \$\endgroup\$ – Erik the Outgolfer Feb 16 '18 at 12:58
  • \$\begingroup\$ Yes, it's exactly the same. If x = g⁻¹yg, then gxg⁻¹ = y, so x and y are conjugates. \$\endgroup\$ – Dennis Feb 16 '18 at 14:27
  • \$\begingroup\$ Hm, I feel like I should reveal my 12-byte solution then: eŒ!ị"Ụị@¥€¥¥ \$\endgroup\$ – Erik the Outgolfer Feb 16 '18 at 14:48
1
\$\begingroup\$

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?
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.