9
\$\begingroup\$

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

Q · P = (1 5)(2 4) · (1 2 4 3) = (1 4 3 5).

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

Wow, this image is massive!

[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.

enter image description here

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]]
\$\endgroup\$
  • \$\begingroup\$ To me, these are permutations, not permutation groups. A permutation group is a collection, closed under this composition operation, of a bunch of individual permutations. \$\endgroup\$ – Greg Martin Apr 5 '17 at 19:51
  • \$\begingroup\$ @GregMartin Fixed terminology \$\endgroup\$ – mbomb007 Apr 5 '17 at 19:56
2
\$\begingroup\$

J, 7 bytes

C.@C.@,

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Your output should be able to be used as your input. \$\endgroup\$ – mbomb007 Sep 27 '17 at 16:43
  • \$\begingroup\$ @mbomb007 The output is usable as input. Each list of cycles has to be a 0-indexed array of boxed arrays. \$\endgroup\$ – miles Sep 27 '17 at 18:35
  • \$\begingroup\$ Or is this J's default print behavior? I just want to make sure the function can be chained. \$\endgroup\$ – mbomb007 Sep 27 '17 at 19:34
  • \$\begingroup\$ @mbomb007 Yes that's just the visual representation of it. It has to be 0-indexed, but I have it listed as 1-indexed and the convert them to 0-index before they are stored in the variables to be passed to the function. Then after, I convert it back from 0-indexed to 1-indexed before outputting it. \$\endgroup\$ – miles Sep 27 '17 at 21:17
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ Thanks for noting that order matters when computing the result. I'd forgotten to add an example or comment about it. That has been rectified. \$\endgroup\$ – mbomb007 Apr 5 '17 at 18:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.