Composition of permutations – the group product

Question

Given two permutations in disjoint cycle form, output their product/composition in disjoint cycle form.

To find the composition, convert the disjoint cycles to permutations in two-line notation. Each number in a disjoint part of a cycle is mapped to the number following it in the same part. It wraps around. So 1 -> 5, 5 -> 1, 2 -> 4, 4 -> 2. If a number is not found, 3 -> 3, it is mapped to itself. The first disjoint cycle could also be written (1 5)(2 4)(3). These mappings are converted to two lines, like so (note that the order of P and Q are reversed):

[T]he product of two permutations is obtained by rearranging the columns of the second (leftmost) permutation so that its first row is identical with the second row of the first (rightmost) permutation. The product can then be written as the first row of the first permutation over the second row of the modified second permutation.

Wikipedia article

---

Rules:

• Input will be given as a list of lists or similar format
• You may not take something like (1 5)(2 4) as [5, 4, 3, 2, 1], already in two-line form (mapping index to value)
• Not all numbers have to occur in each group, so you could have (1 5)·(1 2), resulting in (2 5 1).
• Your output should be able to be used as your input.
• You do not need to support input with an empty cycle (1 5)·(). That would instead be given as (1 5)·(1) or something equivalent.
• Since cycles wrap around, the order doesn't matter as long as the result is correct.
• You can start at zero or one. It doesn't matter, because the results are the same.
• The numbers can be larger than 9.
• You may not include the same number more than once in the output. So [[1],[1]] is not allowed.
• Note that this operation is not commutative! I put Q before P, because that's what Wikipedia did. You can choose any order, but specify which if it's different.
• Shortest code wins
• Built-ins are allowed, but if you use one, show a solution without using it as well.

Examples:

Not all equivalent output possibilities are shown

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

Answer 1

J, 7 bytes

C.@C.@,

Try it online!

Answer 2

Haskell, 157 148 bytes

EDIT:

• -9 bytes: That could indeed be golfed more. Removed redundant parentheses around p++q. Swapped argument order of g. Got rid of d by starting iterate with p x, after which takeWhile no longer tied with fst + span. Made iterate infix.

Doing this while I'm late... probably can golf some more.

It was simpler, and seemed to be allowed, so the output includes single-element cycles.

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

Try it online!

How it works:

• # is the main function. q#p takes two lists of lists of numbers, and returns a similar list. The tests seem to have Q before P so I used the same order.
• f p converts the permutation p from disjoint cycle form to a function, after which f q and f p can be composed with the usual composition operator ..
  • The list comprehension iterates through the cycles c, searching for a and finding its successor. If the comprehension finds nothing, a is just returned.
  • zip(0:c)(c++c) is a list of pairs of elements of c and their successors. Since the question lets us "start at one" we can use 0 as a dummy value; it's cheaper to prepend that to zip's first argument than to use tail on the second.
• g l p takes a list l of elements, and a permutation function p, and returns the list of cycles touching the elements.
  • Here c is the cycle containing the first element x of the list, the other elements of c are found by iterating from p x until x is found again. When recursing to find the remaining cycles, all elements of c are first removed with a list comprehension.

Answer 3

Mathematica, 15 bytes

##⊙Cycles@{}&

Yes Virginia, there is a builtin.... Mathematica supports a permutation data type already in disjoint cycle notation: this pure function takes as input any number of arguments in the form Cycles[{{1, 5}, {2, 4}}] and outputs the product permutation, again in Cycles[] form. It uses the opposite ordering convention as the OP, so for example,

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

returns Cycles[{{1, 4, 3, 5}}]. The ⊙ symbol I used above should really be the 3-byte private-use Unicode symbol U+F3DE to work in Mathematica. Note that Mathematica has a named builtin for this operation, PermutationProduct, but that's three bytes longer.