Сопряженные перестановки

17

Перестановка размера 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
Пост Рок Гарф Хантер
источник
Можем ли мы принять входные данные как функцию? Можем ли мы взять размер n?
xnor
@xnor Конечно, в обоих случаях. Я не уверен, как первый поможет вам, хотя.
Пост Рок Гарф Хантер
Правила ввода функции по умолчанию позволяют предположить, что функция предопределена, что позволяет сэкономить байты при записи ее в качестве аргумента, если вы разрешите это.
xnor
@xnor Мы говорим об этом правиле? Это для функций черного ящика, которые не являются перестановками. Это имеет смысл, потому что этот консенсус разработан, чтобы позволить языкам без указателей / объектов функций конкурировать, тогда как здесь они могут, потому что перестановки могут быть представлены иначе.
Пост Рок Гарф Хантер
Я был, я не думал о том, что они были черным ящиком. Так что здесь, вход может быть функцией, но только как явный аргумент?
xnor

Ответы:

6

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 , из них мы можем восстановить размеры циклов и их кратности. Итак, наша «подпись» идентифицирует перестановку с точностью до сопряжения.

XNOR
источник
6

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
Матиас Долидон
источник
1
Добро пожаловать в PPCG и хороший первый пост. Я сократил ваш метод до 16 байт -:&([:/:~#&>)&C., используя неявную форму. Вот ссылка TIO, чтобы попробовать это.
миль
Спасибо. :) Я все еще начинающий J, и, хотя я, кажется, легко использую его в явных формах, составление эффективных молчаливых форм все еще требует от меня чрезмерных усилий. Я добавлю ваше решение.
Матиас Долидон
PS: разве мы не считаем символы назначения функций? c=:
Матиас Долидон
1
@MathiasDolidon Нет, по общему согласию мы не учитываем символы, необходимые для назначения, поскольку функция может использоваться как есть (с круглыми скобками, но мы не считаем их).
Эрик Outgolfer
1
OK ! Я задним числом обновил количество явных решений в заголовке, чтобы учесть это.
Матиас Долидон
4

MATL , 20 19 17 16 байт

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

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

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

объяснение

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

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

  • Условие x = gyg −1 эквивалентно 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
Луис Мендо
источник
2

Желе , 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.
Деннис
источник
Насколько я понимаю, это на самом деле, yкакие индексы в каждом g⁻¹, а не наоборот. Смотрите пример (4 1 2 3)(2 1 3 4) = (4 2 1 3). При вашем подходе это привело бы к тому (1 4 2 3), что вторые индексируют в первый. Учитывая это, у меня есть 12-байтовое решение, которое я пока не испорчу. :-)
Эрик Outgolfer
@EriktheOutgolfer Исправлено.
Деннис
@Dennis Но я не пришел к такому выводу, основываясь на объяснении, я пришел к точно такому же подходу, за исключением того, что у меня было что-то вроде Œ!©Ụ€⁹ịЀ®ị"⁸e(в основном все индексации с обратными аргументами), за исключением более короткого после того, как я сделал значительные изменения. Я не думаю g⁻¹yg, что так же, как gyg⁻¹. Кроме того, я думаю, что ваш ответ тоже может принести пользу от этих модификаций, но, как я уже говорил, я пока не хочу портить удовольствие.
Эрик Outgolfer
Да, это точно так же. Если x = g⁻¹yg, значит gxg⁻¹ = y, так xи yявляются сопряженными.
Деннис
Хм, я чувствую, что должен раскрыть свое 12-байтовое решение:eŒ!ị"Ụị@¥€¥¥
Эрик Outgolfer
1

Шелуха , 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?
Zgarb
источник
1

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 неправильно пересчитывает свой стек.

Тон Хоспел
источник
1

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 для сравнения массивов. Еще один байт можно сохранить с помощью карри, но я не люблю карри, если только это не куриная тикка масала.

Нил
источник