Biorąc pod uwagę dwie permutacje w formie rozłącznego cyklu, wyprowadzaj ich produkt / skład w formie rozłącznego cyklu.

Aby znaleźć kompozycję, zamień cykle rozłączne na permutacje w notacji dwuwierszowej. Każda liczba w rozłącznej części cyklu jest odwzorowywana na liczbę występującą po niej w tej samej części. Owija się wokół. Więc 1 -> 5, 5 -> 1, 2 -> 4, 4 -> 2. Jeśli liczba nie zostanie znaleziona, 3 -> 3zostanie zamapowana na siebie. Można również napisać pierwszy cykl rozłączny (1 5)(2 4)(3). Te odwzorowania są konwertowane na dwie linie, podobnie jak (zauważ, że kolejność P i Q są odwrócone):

[T] iloczyn dwóch permutacji uzyskuje się przez przestawienie kolumn drugiej permutacji (skrajnie z lewej), tak aby jej pierwszy rząd był identyczny z drugim rzędem pierwszego (skrajnie z prawej) permutacji. Produkt można następnie zapisać jako pierwszy wiersz pierwszej permutacji nad drugim rzędem zmodyfikowanej drugiej permutacji.

Artykuł w Wikipedii

Zasady:

• Dane wejściowe zostaną podane jako lista list lub podobny format
• Być może nie ma czegoś takiego (1 5)(2 4)jak [5, 4, 3, 2, 1], już w postaci dwóch linii (indeks mapowanie wartości)
• Nie wszystkie liczby muszą występować w każdej grupie, więc możesz to zrobić (1 5)·(1 2), w wyniku czego (2 5 1).
• Twoje dane wyjściowe powinny być wykorzystywane jako dane wejściowe.
• Nie trzeba wspierać wprowadzania z pustym cyklem (1 5)·(). To byłoby zamiast tego podane jako (1 5)·(1)lub coś równoważnego.
• Ponieważ cykle się zawijają, kolejność nie ma znaczenia, dopóki wynik jest prawidłowy.
• Możesz zacząć od zera lub jednego. To nie ma znaczenia, ponieważ wyniki są takie same.
• Liczby mogą być większe niż 9.
• Nie można podać tej samej liczby więcej niż raz w danych wyjściowych. Więc [[1],[1]]nie jest dozwolone.
• Pamiętaj, że ta operacja nie jest przemienna ! Stawiam Q przed P., bo tak właśnie zrobiła Wikipedia. Możesz wybrać dowolne zamówienie, ale określ, które z nich jest inne.
• Najkrótszy kod wygrywa
• Wbudowane są dozwolone, ale jeśli go użyjesz, pokaż rozwiązanie bez jego użycia.

Przykłady:

Nie pokazano wszystkich równoważnych możliwości wyjściowych

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 bajtów

C.@C.@,

Wypróbuj online!

Mathematica, 15 bajtów

##⊙Cycles@{}&

Tak, Virginia, jest wbudowany .... Mathematica obsługuje typ danych permutacji już w notacji rozłącznego cyklu: ta czysta funkcja przyjmuje jako dane wejściowe dowolną liczbę argumentów w formularzu Cycles[{{1, 5}, {2, 4}}]i generuje permutację produktu, ponownie w Cycles[]formie. Używa przeciwnej konwencji porządkowania jak OP, więc na przykład

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

zwraca Cycles[{{1, 4, 3, 5}}]. ⊙Symbol użyłem powyżej powinny być naprawdę 3-bajtowy prywatne wykorzystanie symbol Unicode U + F3DE do pracy w Mathematica. Zauważ, że Mathematica ma wbudowaną nazwę dla tej operacji PermutationProduct, ale to trzy bajty dłużej.

Haskell , 157 148 bajtów

EDYTOWAĆ:

• -9 bajtów: To rzeczywiście można by grać w golfa więcej. Usunięto zbędne nawiasy wokół p++q. Zamieniona kolejność argumentów g. Pozbyłem dsię, zaczynając iterateod p x, po czym takeWhilejuż nie związany z fst+ span. Wykonano iterateinfix.

Robię to, kiedy się spóźniłem ... pewnie jeszcze trochę golfa.

To było prostsze i wydawało się być dozwolone, więc wynik zawiera cykle jednoelementowe.

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

Wypróbuj online!

Jak to działa:

• #jest główną funkcją. q#ppobiera dwie listy list liczb i zwraca podobną listę. Testy wydają się mieć Q przed P, więc użyłem tej samej kolejności.
• f pprzekształca permutacji pz postaci cyklu rozłączne do funkcji, po czym f qi f pmoże składać się ze zwykłymi operatora kompozycji ..
  • Zrozumienie listy przechodzi przez cykle c, szukając ai znajdując następcę. Jeśli zrozumienie niczego nie znajdzie, ajest po prostu zwracane.
  • zip(0:c)(c++c)to lista par elementów ci ich następców. Ponieważ pytanie pozwala nam „zacząć od pierwszego”, możemy użyć go 0jako wartości zastępczej; taniej jest wstawić to do zippierwszego argumentu, niż użyć taildrugiego.
• g l ppobiera listę lelementów i funkcję permutacji pi zwraca listę cykli dotykających elementów.
  • Oto ccykl zawierający pierwszy element xlisty, pozostałe elementy cznajdują się poprzez iterację od p xdo do xznalezienia ponownie. Podczas rekurencji w celu znalezienia pozostałych cykli wszystkie elementy csą najpierw usuwane ze zrozumieniem listy.

Python, 220 bajtów

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 bajtów

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,()))})

Wypróbuj online! lub Sprawdź wszystkie przypadki testowe!

Wejście : qi pw tej kolejności, każdy jest zbiorem krotek, z STDIN.
Dane wyjściowe : permutacja produktu Q·Pjako zestaw krotek do STDERR.

Wyjaśnienie

Funkcja gwyszukuje, która liczba odwzorowuje liczbę iw permutacji p(aka gto permutacja odwrotna 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

Funkcja hprzyjmuje liczbę i zwraca cykl Q·Pzawierający tę liczbę. Zwrócony cykl będzie krotką sformatowaną w taki sposób, że najmniejszy element ma indeks 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

Stosując hdo wszystkich liczb, możemy uzyskać wszystkie cykle Q·P. Aby zapobiec powtarzaniu się cykli w naszym wyniku, po prostu umieszczamy wszystkie cykle w zestawie. Działa to, ponieważ podobne cykle zwrócone przez hzostaną sformatowane do tej samej krotki (z najmniejszym elementem o indeksie 0).
Musimy tylko wziąć pod uwagę liczby pojawiające się w Plub Q, ponieważ wszystkie inne liczby zostaną zmapowane do siebie.

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
    )
  }
)