Перестановка размера n является переупорядочением первых n натуральных чисел. (имеется в виду, что каждое целое число появляется один раз и ровно один раз). Перестановки можно рассматривать как функции, которые изменяют порядок списка элементов размера n . Например

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

Таким образом, перестановки могут быть составлены как функции.

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

Это вызывает много интересных свойств. Сегодня мы сосредоточены на сопряженности . Перестановки y и x (оба размера n ) являются сопряженными, если существуют такие перестановки g и g ^-1 (также размера n ), что

x = gyg-1

и gg ^-1 равен тождественной перестановке (первые n чисел в правильном порядке).

Ваша задача - взять две перестановки одинакового размера с помощью стандартных методов ввода и решить, являются ли они сопряженными. Вы должны вывести одно из двух непротиворечивых значений: одно, если они являются сопряженными, и другое, если это не так.

Это код-гольф, поэтому ответы будут оцениваться в байтах, причем меньшее количество байтов будет лучше.

В вашем распоряжении множество теорем о сопряженных перестановках, так что удачи и удачного игры в гольф.

Вы можете принимать входные данные как упорядоченный контейнер значений (1-n или 0-n), представляющих перестановку, как описано выше, или как функцию, которая принимает упорядоченный контейнер и выполняет перестановку. Если вы решите использовать функцию, вы должны принять ее в качестве аргумента, а не иметь предопределенное имя.

Тестовые случаи

(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

Python 2 , 87 байт

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)

Попробуйте онлайн!

Принимает Pв качестве пары как перестановки, так и kих длину. Выходы 1для конъюгатов а 0нет.

Это использует результат:

Две перестановки x и y в точности сопряжены, если их k-й степени x ^k и y ^k имеют одинаковое число неподвижных точек для каждого k от 0 до n .

Две сопряженные перестановки удовлетворяют этому, потому что их k-й степени также сопряжены, и сопряженность сохраняет количество неподвижных точек.

Менее очевидно, что любые две несопряженные перестановки всегда различаются. В частности, сопряженность определяется отсортированным списком длин циклов, и их можно восстановить из числа фиксированных точек. Один из способов показать это с помощью линейной алгебры, хотя это может быть излишним.

Пусть X - матрица перестановок для x . Тогда число неподвижных точек x ^k равно Tr (X ^k ) . Эти следы являются степенными симметричными полиномами собственных значений X ^k с кратностью. Эти полиномы для k от 0 до n позволят нам восстановить соответствующие элементарные симметрические полиномы этих собственных значений, и, следовательно, характеристический полином и, следовательно, сами собственные значения.

Поскольку эти собственные значения являются корнями единицы, соответствующими циклам x , из них мы можем восстановить размеры циклов и их кратности. Итак, наша «подпись» идентифицирует перестановку с точностью до сопряжения.

J , 25 байтов 23 байта 16 байтов

молчаливое решение миль :

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

Явное решение OP:

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

Это проверяет, имеют ли перестановки x и y одинаковый тип цикла, используя встроенную C.функцию для создания представлений цикла.

   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

MATL , 20 19 17 16 байт

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

Вход: два вектора столбцов (используется в ;качестве разделителя). Вывод: 1если сопряжено, 0если нет.

Попробуйте онлайн! Или проверьте все тестовые случаи .

объяснение

Не используются теоремы о перестановках (из-за чистого невежества); просто грубая сила и эти два факта

• Для двух перестановок p и q композиция pq эквивалентна использованию p для индексации элементов q .

• Условие x = gyg ⁻¹ эквивалентно xg = gy .

Код комментария:

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

Wolfram Language (Mathematica) , 44 байта

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

Попробуйте онлайн!

Wolfram Language (Mathematica) , 44 байта

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

Использование кодировки CP-1252, где ±один байт.

Попробуйте онлайн!

Желе , 11 байт

Œ!©Ụ€ịị"®⁸e

Попробуйте онлайн!

Как это устроено

Œ!©Ụ€ịị"®⁸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.

Шелуха , 9 байт

¤¦ṠmöLU¡!

Возвращает 1для сопряженных и 0не сопряженных. Попробуйте онлайн!

объяснение

Класс сопряженности перестановок P из L = [1,2, .., п] определяется мультимножестве , содержащей наименьший период каждого числа в L под P . Когда P берется в виде списка, я могу заменить L на P и получить тот же мультимножество. Программа вычисляет соответствующий мультимножество для каждого входа и проверяет, является ли один подмножеством другого. Поскольку они имеют одинаковое количество элементов, это эквивалентно тому, что они являются одним и тем же мультимножеством.

¤¦Ṡ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?

Perl 61 58 57 байт

Включает +2в себя дляap

Дайте 0-основанные перестановки как 2 строки на 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

Алгоритм - это небольшая вариация алгоритма в решении xnor

Эта более старая версия кода встречается с ошибкой Perl и сбрасывает ядро ​​для нескольких входных данных на моем последнем Perl 5.26.1, но работает на более старом Perl 5.16.3.

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

Возможно, это еще один пример моего старого врага perlgolf, тот факт, что perl неправильно пересчитывает свой стек.

JavaScript (ES6), 66 64 байта

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

Если я правильно прочитал остальные ответы, проблема эквивалентна подсчету периодов всех элементов и проверке того, что два списка имеют одинаковое число для каждого периода. Изменить: 1 байт благодаря @Arnauld, вычисляя на единицу меньше периода. Благодаря @Arnauld удалось сэкономить еще один байт, применив странные правила принуждения JavaScript для сравнения массивов. Еще один байт можно сохранить с помощью карри, но я не люблю карри, если только это не куриная тикка масала.