Étant donné deux permutations sous forme de cycle disjoint, sortez leur produit / composition sous forme de cycle disjoint.

Pour trouver la composition, convertissez les cycles disjoints en permutations en notation à deux lignes. Chaque numéro d'une partie disjointe d'un cycle est mappé sur le numéro qui le suit dans la même partie. Il s'enroule. Alors 1 -> 5, 5 -> 1, 2 -> 4, 4 -> 2. Si un nombre n'est pas trouvé 3 -> 3, il est mappé sur lui-même. Le premier cycle disjoint pourrait également être écrit (1 5)(2 4)(3). Ces mappages sont convertis en deux lignes, comme ceci (notez que l'ordre de P et Q sont inversés):

[Le] produit de deux permutations est obtenu en réorganisant les colonnes de la deuxième permutation (la plus à gauche) de sorte que sa première ligne soit identique à la deuxième ligne de la première permutation (la plus à droite). Le produit peut alors être écrit comme la première ligne de la première permutation sur la deuxième ligne de la deuxième permutation modifiée.

Article Wikipédia

Règles:

• L'entrée sera donnée sous la forme d'une liste de listes ou d'un format similaire
• Vous ne pouvez pas prendre quelque chose comme (1 5)(2 4)as [5, 4, 3, 2, 1], déjà sous forme de deux lignes (mappage de l'index à la valeur)
• Tous les nombres ne doivent pas nécessairement se produire dans chaque groupe, vous pourriez donc avoir (1 5)·(1 2), ce qui entraînerait (2 5 1).
• Votre sortie doit pouvoir être utilisée comme entrée.
• Vous n'avez pas besoin de prendre en charge la saisie avec un cycle vide (1 5)·(). Ce serait plutôt donné comme (1 5)·(1)ou quelque chose d'équivalent.
• Étant donné que les cycles se déroulent, l'ordre n'a pas d'importance tant que le résultat est correct.
• Vous pouvez commencer à zéro ou à un. Ce n'est pas grave, car les résultats sont les mêmes.
• Les nombres peuvent être supérieurs à 9.
• Vous ne pouvez pas inclure le même nombre plus d'une fois dans la sortie. Ce [[1],[1]]n'est donc pas permis.
• Notez que cette opération n'est pas commutative ! J'ai mis Q avant P, parce que c'est ce que Wikipedia a fait. Vous pouvez choisir n'importe quelle commande, mais spécifiez laquelle si elle est différente.
• Victoires de code les plus courtes
• Les fonctions intégrées sont autorisées, mais si vous en utilisez une, montrez une solution sans l'utiliser également.

Exemples:

Toutes les possibilités de sortie équivalentes ne sont pas affichées

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 octets

C.@C.@,

Essayez-le en ligne!

Mathematica, 15 octets

##⊙Cycles@{}&

Oui Virginie, il y a une fonction intégrée .... Mathematica prend en charge un type de données de permutation déjà en notation de cycle disjoint: cette fonction pure prend en entrée n'importe quel nombre d'arguments dans le formulaire Cycles[{{1, 5}, {2, 4}}]et sort la permutation du produit, toujours sous Cycles[]forme. Il utilise la convention de commande opposée à l'OP, donc par exemple,

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

retourne Cycles[{{1, 4, 3, 5}}]. Le ⊙symbole que j'ai utilisé ci-dessus devrait vraiment être le symbole Unicode à usage privé U + F3DE de 3 octets pour fonctionner dans Mathematica. Notez que Mathematica a une fonction intégrée nommée pour cette opération PermutationProduct, mais c'est trois octets de plus.

Haskell , 157 148 octets

ÉDITER:

• -9 octets: cela pourrait en effet être plus joué. Suppression des parenthèses redondantes autour p++q. Ordre des arguments échangés de g. Débarrassé den commençant iteratepar p x, après quoi il takeWhilen'est plus à égalité avec fst+ span. Made iterateinfix.

Faire cela pendant que je suis en retard ... peut probablement jouer au golf encore plus.

C'était plus simple et semblait être autorisé, donc la sortie comprend des cycles à élément unique.

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

Essayez-le en ligne!

Comment ça fonctionne:

• #est la fonction principale. q#pprend deux listes de listes de nombres et renvoie une liste similaire. Les tests semblent avoir Q avant P donc j'ai utilisé le même ordre.
• f pconvertit la permutation pde la forme du cycle disjoint en une fonction, après quoi f qelle f ppeut être composée avec l'opérateur de composition habituel ..
  • La compréhension de la liste parcourt les cycles c, recherchant aet trouvant son successeur. Si la compréhension ne trouve rien, elle aest juste retournée.
  • zip(0:c)(c++c)est une liste de paires d'éléments cet de leurs successeurs. Puisque la question nous permet de «commencer à un», nous pouvons utiliser 0comme valeur fictive; il est moins coûteux d'ajouter ce zippremier argument au premier argument que de l'utiliser tailsur le second.
• g l pprend une liste ld'éléments, et une fonction de permutation p, et retourne la liste des cycles touchant les éléments.
  • Voici cle cycle contenant le premier élément xde la liste, les autres éléments de csont trouvés en itérant de p xjusqu'à ce que xsoit retrouvé. Lors de la récurrence pour trouver les cycles restants, tous les éléments de csont d'abord supprimés avec une liste de compréhension.

Python, 220 octets

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 octets

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

Essayez-le en ligne! ou Vérifiez tous les cas de test!

Entrée : qet pdans cet ordre, chacun est un ensemble de tuples, deSTDIN .
Sortie : permutation du produit Q·Psous la forme d'un ensemble de tuples, vers STDERR.

Explication

La fonction gtrouve quel nombre correspond au nombre idans la permutation p(akag est la permutation inverse de 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

La fonction h prend un nombre et renvoie le cycle Q·Pqui contient ce nombre. Le cycle renvoyé sera un tuple, formaté de manière à ce que le plus petit élément soit à l'index 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

En appliquant hà tous les numéros, nous pouvons obtenir tous les cycles Q·P. Pour éviter les cycles en double dans notre résultat, nous plaçons simplement tous les cycles dans un ensemble. Cela fonctionne car des cycles similaires retournés par hseront formatés sur le même tuple (avec le plus petit élément à l'index 0).
Nous avons seulement besoin de considérer les nombres apparaissant dans Pou Q, car tous les autres nombres se mapperont à eux-mêmes.

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