Учитывая две перестановки в форме непересекающегося цикла, выведите их произведение / композицию в форме непересекающегося цикла.

Чтобы найти композицию, преобразуйте непересекающиеся циклы в перестановки в двухстрочной записи. Каждое число в непересекающейся части цикла отображается на число, следующее за ним в той же части. Это оборачивается. Так 1 -> 5, 5 -> 1, 2 -> 4, 4 -> 2. Если число не найдено 3 -> 3, оно отображается на себя. Первый непересекающийся цикл также может быть записан (1 5)(2 4)(3). Эти отображения преобразуются в две строки, например, так (обратите внимание, что порядок P и Q поменялся местами):

[T] произведение двух перестановок получается путем перестановки столбцов второй (самой левой) перестановки так, чтобы ее первая строка совпадала со второй строкой первой (самой правой) перестановки. Затем произведение может быть записано как первая строка первой перестановки над второй строкой модифицированной второй перестановки.

Статья в википедии

Правила:

• Ввод будет предоставлен в виде списка списков или аналогичного формата
• Вы не можете принимать что-то вроде (1 5)(2 4)as [5, 4, 3, 2, 1], уже в двухстрочной форме (отображение индекса на значение)
• Не все числа должны встречаться в каждой группе, так что вы могли бы иметь (1 5)·(1 2), в результате (2 5 1).
• Ваш вывод должен быть в качестве вашего ввода.
• Вам не нужно поддерживать ввод с пустым циклом (1 5)·(). Это вместо этого будет дано (1 5)·(1)или как что-то эквивалентное.
• Поскольку циклы повторяются, порядок не имеет значения, пока результат правильный.
• Вы можете начать с нуля или единицы. Это не имеет значения, потому что результаты одинаковы.
• Числа могут быть больше, чем 9.
• Вы не можете включать один и тот же номер более одного раза в вывод. Так [[1],[1]]что не допускается.
• Обратите внимание, что эта операция не является коммутативной ! Я поставил Q перед P, потому что это то, что сделал Википедия. Вы можете выбрать любой заказ, но указать, какой, если он отличается.
• Самый короткий код выигрывает
• Встроенные модули разрешены, но если вы их используете, покажите решение, не используя его.

Примеры:

Не все эквивалентные возможности вывода показаны

Input
Output

[[1, 5], [2, 4]], [[1, 2, 4, 3]]
[[1, 4, 3, 5]] (or [[4, 3, 5, 1]] or ...)

[[1, 5]], [[1, 2]]
[[2, 5, 1]]

[[10, 2, 3]], [[2]]
[[3, 10, 2]]

[[1]], [[3]]
[[]] (or [[1]] or something equivalent)

[[10,2,3,15],[1,7],[5,6],[14,4,13,11,12]], [[5,6,7,9,14],[2,8,3,10],[1,11]]
[[12, 14, 6, 1], [8, 15, 10, 3, 2], [13, 11, 7, 9, 4]]

(arguments in reverse order from above gives a different answer)
[[5,6,7,9,14],[2,8,3,10],[1,11]], [[10,2,3,15],[1,7],[5,6],[14,4,13,11,12]]
[[9, 14, 4, 13, 1], [10, 8, 3, 15, 2], [7, 11, 12, 5]]

J 7 байт

C.@C.@,

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

Mathematica, 15 байт

##⊙Cycles@{}&

Да, Вирджиния, есть встроенная функция .... Mathematica поддерживает тип данных перестановки, который уже находится в записи непересекающегося цикла: эта чистая функция принимает в качестве входных данных любое количество аргументов в форме Cycles[{{1, 5}, {2, 4}}]и выводит перестановку продуктов, снова в Cycles[]форме. Он использует соглашение об обратном порядке в качестве OP, например,

##⊙Cycles@{}&[Cycles[{{1, 2, 4, 3}}], Cycles[{{1, 5}, {2, 4}}]]

возвращается Cycles[{{1, 4, 3, 5}}]. ⊙Символ я выше должен действительно быть 3-байтовый частного использования Unicode символ U + F3DE для работы в Mathematica. Обратите внимание, что Mathematica имеет именованную встроенную функцию для этой операции PermutationProduct, но это на три байта длиннее.

Хаскелл , 157 148 байт

РЕДАКТИРОВАТЬ:

• -9 байт: это действительно может быть больше в гольфе. Убраны лишние скобки вокруг p++q. Поменялся местами порядок аргументов g. Избавился d, начав iterateс того p x, после чего takeWhileперестал связывать fst+ span. Сделал iterateинфикс.

Занимаясь этим, пока я опаздываю ... возможно, могу еще поиграть в гольф.

Это было проще и казалось разрешенным, поэтому выходные данные включают одноэлементные циклы.

q#p=g(p++q>>=id)$f q.f p
f p a=last$a:[y|c<-p,(x,y)<-zip(0:c)(c++c),x==a]
g(x:l)p|c<-x:fst(span(/=x)$p`iterate`p x)=c:g[x|x<-l,x`notElem`c]p
g[]p=[]

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

Как это работает:

• # это основная функция. q#pберет два списка списков чисел и возвращает аналогичный список. Тесты, кажется, имеют Q до P, поэтому я использовал тот же порядок.
• f pпреобразует перестановку pиз непересекающейся формы цикла в функцию, после чего f qи f pможет быть составлена ​​с помощью обычного оператора композиции. .
  • Понимание списка перебирает циклы c, ища aи находя его преемника. Если понимание ничего не находит,a просто возвращается.
  • zip(0:c)(c++c)список пар элементов cи их наследников Поскольку вопрос позволяет нам «начинать с одного», мы можем использовать 0в качестве фиктивного значения; дешевле добавить это к zipпервому аргументу, чем использовать tailко второму.
• g l pпринимает список lэлементов и функцию перестановки pи возвращает список циклов, касающихся элементов.
  • Вот cцикл, содержащий первый элемент xсписка, другие элементы которого cнаходятся путем итерации, p xпока не xбудет найден снова. При повторном поиске оставшихся циклов все элементы cсначала удаляются с пониманием списка.

Python, 220 байт

a,b=eval(input())
p,o=a+b,[]
for i in range(1,1+max(map(max,p))):
 if not any(i in t for t in o):
  u,m=(i,),i
  while 1:
   for t in p[::-1]:
    if m in t:m=t[(t.index(m)+1)%len(t)]
   if m==i:o+=[u];break
   u+=(m,)
o

Python 3,8 , 187 байт

q,p=eval(input())
g=lambda p,i:[*(c[c.index(i)-1]for c in p if i in c),i][0]
h=lambda*c:(x:=g(p,g(q,c[0])))in c and(*c[(m:=c.index(min(c))):],*c[:m])or h(x,*c)
exit({*map(h,sum(p|q,()))})

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

Входные данные : qи pв этом порядке, каждый представляет собой набор кортежей, из STDIN.
Вывод : перестановка произведений Q·Pв виде набора кортежей, до STDERR.

объяснение

Функция gнаходит, какое число отображается на число iв перестановке p(aka g- обратная перестановка p).

g=lambda p,i:        
[                   # creates a list
  *(                # containing the following
    c[c.index(i)-1] #   the number before i in cycle c
    for c in p      #   for all cycles in permutation
    if i in c       #   if i is in that cycle
  )                 #
  ,i                # adds i to the end of that list
                    #   (in case i is not in any cycle)
][0]                # returns the first element of the list

Функция hпринимает число и возвращает цикл, в Q·Pкотором содержится это число. Возвращенный цикл будет кортежем, отформатированным таким образом, чтобы наименьший элемент имел индекс 0.

h=lambda*c:                   # input: an incomplete cycle c, as a list
(x:=g(p,g(q,c[0])))           # finds the number x before the first number in c
in c                          # if x is also in c (aka the cycle is complete)
and                           # then returns the following:
(                             #   c as a tuple with min element at index 0
  *c[(m:=c.index(min(c))):],  #   (c, from the min element to the end)
  *c[:m]                      #   (c, from start to the min element)
)
or                            # else (cycle is incomplete) returns the following
h(x,*c)                       #   recursive result when after prepending x to c

Применяя hко всем числам, мы можем получить все циклы Q·P. Чтобы избежать дублирования циклов в нашем результате, мы просто помещаем все циклы в набор. Это работает, поскольку похожие циклы, возвращаемые функцией, hбудут отформатированы в один и тот же кортеж (с наименьшим элементом с индексом 0).
Нам нужно только рассмотреть числа, появляющиеся в Pили Q, так как все остальные числа будут отображаться на себя.

exit(              # returns through STDERR
  {                # create a set from the followings
    *map(h,        #   map function h to
      sum(p|q,())  #   all numbers in P or Q
    )
  }
)