Dadas dos permutaciones en forma de ciclo disjunto, envíe su producto / composición en forma de ciclo disjunto.

Para encontrar la composición, convierta los ciclos disjuntos en permutaciones en notación de dos líneas. Cada número en una parte disjunta de un ciclo se asigna al número que le sigue en la misma parte. Se envuelve. Así 1 -> 5, 5 -> 1, 2 -> 4, 4 -> 2. Si no se encuentra un número 3 -> 3, se asigna a sí mismo. El primer ciclo disjunto también podría escribirse (1 5)(2 4)(3). Estas asignaciones se convierten en dos líneas, así (tenga en cuenta que el orden de P y Q se invierte):

[E] l producto de dos permutaciones se obtiene reorganizando las columnas de la segunda permutación (más a la izquierda) de modo que su primera fila sea idéntica a la segunda fila de la primera permutación (más a la derecha). El producto puede entonces escribirse como la primera fila de la primera permutación sobre la segunda fila de la segunda permutación modificada.

Artículo de Wikipedia

Reglas:

• La entrada se dará como una lista de listas o formato similar
• Es posible que no tome algo así (1 5)(2 4)como [5, 4, 3, 2, 1], ya en forma de dos líneas (asignación de índice a valor)
• No todos los números tienen que aparecer en cada grupo, por lo que podría haber (1 5)·(1 2)resultado (2 5 1).
• Su salida debe poder usarse como su entrada.
• No necesita admitir entradas con un ciclo vacío (1 5)·(). Eso se daría como (1 5)·(1)algo equivalente.
• Dado que los ciclos se ajustan, el orden no importa siempre que el resultado sea correcto.
• Puede comenzar en cero o uno. No importa, porque los resultados son los mismos.
• Los números pueden ser mayores que 9.
• No puede incluir el mismo número más de una vez en la salida. Entonces [[1],[1]]no está permitido.
• ¡Tenga en cuenta que esta operación no es conmutativa ! Puse Q antes que P, porque eso es lo que hizo Wikipedia. Puede elegir cualquier orden, pero especifique cuál es diferente.
• El código más corto gana
• Los elementos integrados están permitidos, pero si usa uno, muestre una solución sin usarlo también.

Ejemplos:

No se muestran todas las posibilidades de salida equivalentes

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.@,

Pruébalo en línea!

Mathematica, 15 bytes

##⊙Cycles@{}&

Sí, Virginia, hay una función incorporada ... Mathematica admite un tipo de datos de permutación que ya está en notación de ciclo disjunto: esta función pura toma como entrada cualquier número de argumentos en el formulario Cycles[{{1, 5}, {2, 4}}]y genera la permutación del producto, nuevamente enCycles[] forma. Utiliza la convención de orden opuesta como OP, por ejemplo,

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

vuelve Cycles[{{1, 4, 3, 5}}]. El ⊙símbolo que utilicé anteriormente realmente debería ser el símbolo Unicode de uso privado de 3 bytes U + F3DE para trabajar en Mathematica. Tenga en cuenta que Mathematica tiene un nombre incorporado para esta operación PermutationProduct, pero eso es tres bytes más.

Haskell , 157148 bytes

EDITAR:

• -9 bytes: eso podría ser más golf. Se eliminaron los paréntesis redundantes p++q. Orden de argumento intercambiado de g. Se deshizo dcomenzando iteratecon p x, después de lo cual takeWhileya no está empatado con fst+ span. Hecho iterateinfijo.

Hacer esto mientras llego tarde ... probablemente pueda jugar al golf un poco más.

Era más simple y parecía estar permitido, por lo que la salida incluye ciclos de un solo elemento.

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

Pruébalo en línea!

Cómo funciona:

• #Es la función principal. q#ptoma dos listas de listas de números y devuelve una lista similar. Las pruebas parecen tener Q antes de P, así que usé el mismo orden.
• f pconvierte la permutación pde forma ciclo disjuntos a una función, después de lo cual f qy f ppuede estar compuesto con el operador de composición usual. .
  • La comprensión de la lista itera a través de los ciclos c, buscando ay encontrando a su sucesor. Si la comprensión no encuentra nada, asolo se devuelve.
  • zip(0:c)(c++c)es una lista de pares de elementos cy sus sucesores. Como la pregunta nos permite "comenzar en uno", podemos usarlo 0como un valor ficticio; es más barato anteponer eso al zipprimer argumento que usarlo tailen el segundo.
• g l ptoma una lista lde elementos y una función de permutación p, y devuelve la lista de ciclos que tocan los elementos.
  • Aquí cestá el ciclo que contiene el primer elemento xde la lista, los otros elementos cse encuentran iterando desde p xhasta que xse encuentre nuevamente. Al recurrir para encontrar los ciclos restantes, todos los elementos de cse eliminan primero con una lista de comprensión.

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

Pruébalo en línea! o ¡ Verifique todos los casos de prueba!

Entrada : qy pen ese orden, cada uno es un conjunto de tuplas, desde STDIN.
Salida : La permutación del producto Q·Pcomo un conjunto de tuplas, a STDERR.

Explicación

La función gencuentra qué número se asigna al número ien la permutación p(también conocido como gla permutación inversa 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 función htoma un número y devuelve el ciclo Q·Pque contiene ese número. El ciclo devuelto será una tupla, formateada de tal manera que el elemento más pequeño esté en el índice 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

Al aplicar ha todos los números, podemos obtener todos los ciclos Q·P. Para evitar ciclos duplicados en nuestro resultado, simplemente colocamos todos los ciclos en un conjunto. Esto funciona ya que los ciclos similares devueltos por hserán formateados a la misma tupla (con el elemento más pequeño en el índice 0).
Solo necesitamos considerar los números que aparecen en Po Q, ya que todos los demás números se asignarán a sí mismos.

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