Bei zwei Permutationen in disjunkter Zyklusform geben Sie ihr Produkt / ihre Zusammensetzung in disjunkter Zyklusform aus.

Um die Komposition zu finden, konvertieren Sie die disjunkten Zyklen in Permutationen in zweizeiliger Notation. Jede Nummer in einem disjunkten Teil eines Zyklus wird der darauf folgenden Nummer im selben Teil zugeordnet. Es wickelt sich herum. Also 1 -> 5, 5 -> 1, 2 -> 4, 4 -> 2. Wenn eine Nummer nicht gefunden wird 3 -> 3, wird sie sich selbst zugeordnet. Der erste disjunkte Zyklus könnte auch geschrieben werden (1 5)(2 4)(3). Diese Zuordnungen werden wie folgt in zwei Zeilen konvertiert (beachten Sie, dass die Reihenfolge von P und Q umgekehrt ist):

Das Produkt zweier Permutationen wird erhalten, indem die Spalten der zweiten (ganz links) Permutation so angeordnet werden, dass ihre erste Reihe mit der zweiten Reihe der ersten (ganz rechts) Permutation identisch ist. Das Produkt kann dann als erste Zeile der ersten Permutation über die zweite Zeile der modifizierten zweiten Permutation geschrieben werden.

Wikipedia-Artikel

Regeln:

• Die Eingabe erfolgt als Liste von Listen oder ähnlichem Format
• Sie können nicht so etwas wie nehmen , (1 5)(2 4)wie [5, 4, 3, 2, 1]bereits in zwei Online-Formular (Mapping - Index - Wert)
• Es müssen nicht alle Zahlen in jeder Gruppe vorkommen, also könnte dies der (1 5)·(1 2)Fall sein (2 5 1).
• Ihre Ausgabe sollte als Eingabe verwendet werden können.
• Sie müssen die Eingabe nicht mit einem leeren Zyklus unterstützen (1 5)·(). Das wäre stattdessen als (1 5)·(1)oder etwas Äquivalentes gegeben.
• Da Zyklen umlaufen, spielt die Reihenfolge keine Rolle, solange das Ergebnis korrekt ist.
• Sie können bei Null oder Eins beginnen. Es spielt keine Rolle, da die Ergebnisse gleich sind.
• Die Zahlen können größer sein als 9.
• Sie dürfen dieselbe Nummer nicht mehr als einmal in die Ausgabe aufnehmen. Also [[1],[1]]ist nicht erlaubt.
• Beachten Sie, dass diese Operation nicht kommutativ ist ! Ich habe Q vor P gesetzt, weil Wikipedia das getan hat. Sie können eine beliebige Reihenfolge wählen, aber angeben, welche, wenn es anders ist.
• Der kürzeste Code gewinnt
• Eingebaute sind zulässig, aber wenn Sie eine verwenden, zeigen Sie eine Lösung, ohne sie ebenfalls zu verwenden.

Beispiele:

Es werden nicht alle äquivalenten Ausgabemöglichkeiten angezeigt

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 Bytes

C.@C.@,

Probieren Sie es online aus!

Mathematica, 15 Bytes

##⊙Cycles@{}&

Ja, Virginia, es gibt eine integrierte Funktion ... Mathematica unterstützt einen Permutationsdatentyp, der bereits in disjunkter Zyklusnotation vorliegt: Diese reine Funktion verwendet eine beliebige Anzahl von Argumenten im Formular als Eingabe Cycles[{{1, 5}, {2, 4}}]und gibt die Produktpermutation erneut in Cycles[]Form aus. Es verwendet die entgegengesetzte Ordnungskonvention als OP, so zum Beispiel

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

kehrt zurück Cycles[{{1, 4, 3, 5}}]. Das ⊙Symbol, das ich oben verwendet habe, sollte eigentlich das 3-Byte-Unicode-Symbol U + F3DE für den privaten Gebrauch sein, um in Mathematica zu arbeiten. Beachten Sie, dass Mathematica einen benannten Namen für diese Operation hat PermutationProduct, der jedoch drei Bytes länger ist.

Haskell , 157 148 Bytes

BEARBEITEN:

• -9 Bytes: Das könnte in der Tat mehr Golf gespielt werden. Redundante Klammern wurden entfernt p++q. Vertauschte Argumentreihenfolge von g. Losgeworden ddurch beginnend iteratemit p x, wonach takeWhilenicht mehr mit gebundenen fst+ span. Hergestellt iterateInfix.

Wenn ich das mache, während ich zu spät bin ... kann ich wahrscheinlich noch mehr Golf spielen.

Es war einfacher und schien erlaubt zu sein, daher enthält die Ausgabe Einzelelementzyklen.

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

Probieren Sie es online aus!

Wie es funktioniert:

• #ist die Hauptfunktion. q#pNimmt zwei Listen mit Zahlenlisten und gibt eine ähnliche Liste zurück. Die Tests scheinen Q vor P zu haben, also habe ich die gleiche Reihenfolge verwendet.
• f pwandelt die Permutation pvon der disjunkten Zyklusform in eine Funktion um, wonach f qundf p kann mit dem üblichen Kompositionsoperator komponiert werden ..
  • Das Listenverständnis durchläuft die Zyklen cund sucht aund findet seinen Nachfolger. Wenn das Verständnis nichts findet, awird es einfach zurückgegeben.
  • zip(0:c)(c++c)ist eine Liste von Elementpaaren cund deren Nachfolgern. Da die Frage uns "bei eins beginnen" lässt, können wir 0als Dummy-Wert verwenden; Es ist billiger, dies dem zipersten Argument voranzustellen als taildem zweiten.
• g l pNimmt eine Liste lvon Elementen und eine Permutationsfunktion pund gibt die Liste der Zyklen zurück, die die Elemente berühren.
  • Hier cist der Zyklus, der das erste Element xder Liste enthält. Die anderen Elemente von cwerden durch Iteration von p xbis xgefunden. Wenn Sie rekursiv nach den verbleibenden Zyklen suchen, werden zunächst alle Elemente von cmit einem Listenverständnis entfernt.

Python, 220 Bytes

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 Bytes

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

Probieren Sie es online aus! oder Überprüfen Sie alle Testfälle!

Eingang : qund pin dieser Reihenfolge ist jedes eine Reihe von Tupeln aus STDIN.
Ausgabe : Die Produktpermutation Q·Pals Satz von Tupeln, um STDERR.

Erläuterung

Die Funktion g , welche Zahl der Zahl iin der Permutation zugeordnet ist p(auch bekannt gals die inverse Permutation von 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

Die Funktion hnimmt eine Zahl auf und gibt den Zyklus zurück Q·P, der diese Zahl enthält. Der zurückgegebene Zyklus ist ein Tupel, das so formatiert ist, dass sich das kleinste Element am Index 0 befindet.

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

Durch Anwenden hauf alle Zahlen können wir alle Zyklen erhalten Q·P. Um doppelte Zyklen in unserem Ergebnis zu vermeiden, setzen wir einfach alle Zyklen in eine Menge. Dies funktioniert, da ähnliche Zyklen, die von zurückgegeben hwerden, mit demselben Tupel formatiert werden (mit dem kleinsten Element am Index 0).
Wir müssen nur die Zahlen berücksichtigen, die in Poder erscheinen Q, da alle anderen Zahlen sich selbst zuordnen.

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