Codegolf - Состав Перестановок - Групповой Продукт

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

Чтобы найти композицию, преобразуйте непересекающиеся циклы в перестановки в двухстрочной записи. Каждое число в непересекающейся части цикла сопоставляется с числом, следующим за ним в той же части. Оно обволакивает. Так

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

, [[1],[1]] , 9 , (1 5)·(1) . Если номер не найден, (1 5)·() , it is mapped to itself. The first disjoint cycle could also be written (2 5 1) . Эти сопоставления преобразуются в две строки, например (обратите внимание, что порядок П и вопрос перевернуты):

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

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

---

Правила:

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

Примеры:

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

1 -> 5

#код-гольф #перестановки #абстрактная-алгебра

Математика, 15 байт

 
 
 
 
 
 
 
 
 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

)

}
)
 
 
 
 
 
 
 
 
 

Да, Вирджиния, есть встроенная функция.... Mathematica поддерживает тип данных перестановки уже в нотации непересекающегося цикла: эта чистая функция принимает на вход любое количество аргументов в форме Q and outputs the product permutation, again in P форма. Он использует противоположное соглашение о порядке, как и OP, например:

h

возвращает Q·P . The h Символ, который я использовал выше, на самом деле должен быть 3-байтовым символом Unicode частного использования U + F3DE для работы в Mathematica. Обратите внимание, что в системе Mathematica для этой операции имеется именованная встроенная функция: 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 , but that's three bytes longer.

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

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

• -9 байт: Действительно, можно было бы сыграть больше. Удалены лишние круглые скобки вокруг Q·P . Swapped argument order of h . Избавился от 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 by starting p с g , after which p больше не связан с i + g . Сделал STDERR infix.

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

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

Q·P

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

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

• STDIN is the main function. p принимает два списка списков чисел и возвращает аналогичный список. Кажется, в тестах Q стоит перед P, поэтому я использовал тот же порядок.
• q converts the permutation 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,()))}) от формы непересекающегося цикла к функции, после чего 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 and C.@C.@, можно составить с помощью обычного оператора композиции c .
  • Понимание списка повторяется по циклам x , searching for p x и найти его преемника. Если понимание ничего не находит, c is just returned.
  • x is a list of pairs of elements of c и их преемники. Поскольку вопрос позволяет нам «начать с одного», мы можем использовать p as a dummy value; it's cheaper to prepend that to l первый аргумент, чем использовать g l p on the second.
• tail takes a list zip элементов и функция перестановки 0 , and returns the list of cycles touching the elements.
  • Здесь c is the cycle containing the first element zip(0:c)(c++c) списка, остальные элементы a are found by iterating from a до c is found again. When recursing to find the remaining cycles, all elements of . сначала удаляются с помощью понимания списка.

Дж, 7 байт

f p

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

Питон, 220 байт

f q ||answer||

Питон 3.8, 187 байт

p

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

Вход: f p and q#p в этом порядке каждый представляет собой набор кортежей, начиная с # .
Выход: Перестановка продукта 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=[] as a set of tuples, to iterate .

Объяснение

Функция span finds which number maps to the number fst в перестановке takeWhile (aka p x является обратной перестановкой iterate ).

d

Функция g takes in a number, and returns the cycle in p++q который содержит это число. Возвращенный цикл будет кортежем, отформатированным таким образом, чтобы наименьший элемент имел индекс 0.

PermutationProduct

Применив ⊙ to all numbers, we can get all cycles in Cycles[{{1, 4, 3, 5}}] . Чтобы предотвратить дублирование циклов в нашем результате, мы просто помещаем все циклы в набор. Это работает, поскольку аналогичные циклы возвращаются ##⊙Cycles@{}&[Cycles[{{1, 2, 4, 3}}], Cycles[{{1, 5}, {2, 4}}]] will be formatted to the same tuple (with the smallest element at index 0).
Нам нужно только рассмотреть числа, встречающиеся в Cycles[] or Cycles[{{1, 5}, {2, 4}}] , поскольку все остальные числа будут отображаться сами на себя.

##⊙Cycles@{}&