1
$\begingroup$

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;
       @lPopped = @lPopped.head(@lPopped.elems - 1);
       @gPopped = @gPopped.head(@gPopped.elems - 1);
     } else {
        my $gDigit = @gPopped.tail;
        @sum.append: $gDigit + $carry;
        $carry = 0;
        @gPopped = @gPopped.head(@gPopped.elems - 1);
     }
   }
   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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

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.