# What easy algorithms are there for calculating products of cycle decompositions?

Here is the easy algorithm we are taught for adding two numbers in base-10 notation. We are taught this algorithm in first or second grade.

  sub infix:<+>(@x, @y) {
#x, y are lists of digits
#returns a list of digits
my @greater = (@y.elems > @x.elems) ?? @y !! @x;
my @lesser_ = (@y.elems > @x.elems) ?? @x !! @y;
my @gPopped = @greater;
my @lPopped = @lesser_;
my $$carry = 0; my @sum; loop (my$$i = 0; $$i < @greater.elems;$$i++) {
if (@lPopped.elems >= 1) {
my $$gDigit = @gPopped.tail; my$$lDigit = @lPopped.tail;
@sum.append: (($$gDigit +$$lDigit) % 10) + $$carry;$$carry = (($$gDigit +$$lDigit) / 10).floor;
} else {
my $$gDigit = @gPopped.tail; @sum.append:$$gDigit + $$carry;$$carry = 0;
}
}
return @sum.reverse;
}


The algorithm is very easy and a child can do it by hand. Meanwhile, I am unaware of any algorithm for multiplying two permutations decomposed into cycle form (e.g. $$(123)\times(12)(34)$$). What is an easy algorithm for multiplying two cycles?

Here is how I would do it manually, taking the example of $$(123) \cdot (12)(34)$$.

Start with a number appearing on the right permutation, say 1. The right permutation sends it to 2, and the left to 3.

Doing the same with 3, we get 4 and then 4.

Doing the same with 4, we get 3 then 1. We have closed a cycle $$(134)$$.

Now take another number on the right (or left) permutation not already covered – has to be 2. It gets sent to 1 then 2. We have closed a cycle – 2 is a fixed point.

In total, the result is $$(134)$$.

Now let's compute $$(12)(34) \cdot (123)$$.

Let's start with 1. It goes to 2 then 1. So it's a fixed point.

Let's try 2 next. It goes to 3 then 4, which goes to itself then 3, which goes to 1 then 2. We have closed a cycle $$(243)$$. That's the answer.