Dadas duas permutações na forma de ciclo separado, produza seu produto / composição na forma de ciclo separado.

Para encontrar a composição, converta os ciclos disjuntos em permutações em notação de duas linhas. Cada número em uma parte separada de um ciclo é mapeado para o número seguinte na mesma parte. Envolve. Assim 1 -> 5, 5 -> 1, 2 -> 4, 4 -> 2. Se um número não for encontrado 3 -> 3, ele será mapeado para si mesmo. O primeiro ciclo separado também pode ser escrito (1 5)(2 4)(3). Esses mapeamentos são convertidos em duas linhas, assim (observe que a ordem de P e Q é invertida):

[O] produto de duas permutações é obtido reorganizando as colunas da segunda permutação (mais à esquerda), de modo que sua primeira linha seja idêntica à segunda linha da primeira permutação (à direita). O produto pode então ser escrito como a primeira linha da primeira permutação sobre a segunda linha da segunda permutação modificada.

Artigo da Wikipedia

Regras:

• A entrada será fornecida como uma lista de listas ou formato semelhante
• Você não pode levar algo (1 5)(2 4)como[5, 4, 3, 2, 1] , já em forma de duas linhas (índice de mapeamento para valor)
• Nem todos os números precisam ocorrer em cada grupo; portanto, você pode ter (1 5)·(1 2), resultando em(2 5 1) .
• Sua saída deve poder ser usada como sua entrada.
• Você não precisa dar suporte à entrada com um ciclo vazio (1 5)·(). Em vez disso, isso seria dado como(1 5)·(1) ou algo equivalente.
• Como os ciclos são concluídos, o pedido não importa, desde que o resultado esteja correto.
• Você pode começar em zero ou um. Não importa, porque os resultados são os mesmos.
• Os números podem ser maiores que 9.
• Você não pode incluir o mesmo número mais de uma vez na saída. Então [[1],[1]]não é permitido.
• Observe que esta operação não é comutativa ! Coloquei Q antes de P, porque foi o que a Wikipedia fez. Você pode escolher qualquer ordem, mas especifique qual é a diferença.
• O código mais curto vence
• Os internos são permitidos, mas se você usar um, mostre uma solução sem usá-la também.

Exemplos:

Nem todas as possibilidades de saída equivalentes são mostradas

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

Experimente online!

Mathematica, 15 bytes

##⊙Cycles@{}&

Sim, Virgínia, existe um .... O Mathematica suporta um tipo de dados de permutação já em notação de ciclo separado: essa função pura recebe como entrada qualquer número de argumentos no formulário Cycles[{{1, 5}, {2, 4}}]e gera a permutação do produto, novamente no Cycles[]formulário. Ele usa a convenção de pedidos oposta como o OP, por exemplo,

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

retorna Cycles[{{1, 4, 3, 5}}]. O ⊙símbolo que usei acima deve realmente ser o símbolo Unicode de uso privado de 3 bytes U + F3DE para funcionar no Mathematica. Observe que o Mathematica possui um built-in nomeado para esta operação PermutationProduct, mas são três bytes a mais.

Haskell , 157 148 bytes

EDITAR:

• -9 bytes: Isso poderia realmente ser mais praticado. Removidos parênteses redundantes ao redor p++q. Ordem de argumento trocada de g. Livre-se de dcomeçar iteratecom p x, após o qual takeWhilenão será mais vinculado com fst+ span. iterateInfix feito .

Fazendo isso enquanto estou atrasado ... provavelmente pode jogar golfe um pouco mais.

Como era mais simples e parecia permitido, a saída inclui ciclos de elemento único.

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

Experimente online!

Como funciona:

• #é a função principal. q#ppega duas listas de números e retorna uma lista semelhante. Os testes parecem ter Q antes de P, então usei a mesma ordem.
• f pconverte a permutação pda forma de ciclo separado em uma função, após a qual f qe f ppode ser composta com o operador de composição usual. .
  • A compreensão da lista percorre os ciclos c, procurando ae encontrando seu sucessor. Se a compreensão não encontrar nada, aé apenas retornado.
  • zip(0:c)(c++c)é uma lista de pares de elementos ce seus sucessores. Como a pergunta nos permite "começar de uma vez", podemos usar 0como um valor fictício; é mais barato acrescentar esse zipprimeiro argumento do que usá-lo tailno segundo.
• g l ppega uma lista lde elementos e uma função de permutaçãop e retorna a lista de ciclos que tocam nos elementos.
  • Aqui cestá o ciclo que contém o primeiro elemento xda lista, os outros elementos de csão encontrados iterando de p xaté que xseja encontrado novamente. Ao recorrer para encontrar os ciclos restantes, todos os elementos de csão removidos primeiro com uma compreensão da lista.

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

Experimente online! ou Verifique todos os casos de teste!

Entrada : qe pnessa ordem, cada um é um conjunto de tuplas, de STDIN.
Saída : a permutação do produto Q·Pcomo um conjunto de tuplas, paraSTDERR .

Explicação

A função glocaliza qual número é mapeado para o número ina permutação p(aka gé a permutação 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

A função hrecebe um número e retorna o ciclo Q·Pque contém esse número. O ciclo retornado será uma tupla, formatada de forma que o menor elemento esteja no í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

Aplicando ha todos os números, podemos obter todos os ciclos Q·P. Para evitar ciclos duplicados em nosso resultado, simplesmente colocamos todos os ciclos em um conjunto. Isso funciona, pois ciclos semelhantes retornados por hserão formatados para a mesma tupla (com o menor elemento no índice 0).
Só precisamos considerar os números que aparecem em Pou Q, como todos os outros números serão mapeados para eles mesmos.

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