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

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.

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

J, 7 bytes

C.@C.@,

Try it online!

Answer 4

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

Answer 5

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

Try it online! or Check all test cases!

Input: q and p in that order, each is a set of tuples, from STDIN.
Output: The product permutation Q·P as a set of tuples, to STDERR.

Explanation

The function g finds which number maps to the number i in the permutation p (aka g is the inverse permutation of 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

The function h takes in a number, and returns the cycle in Q·P that contains that number. The returned cycle will be a tuple, formatted in a way such that the smallest element is at 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

By applying h to all numbers, we can get all cycles in Q·P. To prevent duplicate cycles in our result, we simply put all cycles in a set. This works since similar cycles returned by h will be formatted to the same tuple (with the smallest element at index 0).
We only needs to consider the numbers appearing in P or Q, as all other numbers will map to themselves.

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