Scala implementation of a finite permutation group

gistfile1.txt

import scala.language.implicitConversions
import scala.language.postfixOps

sealed trait Permutation[+A]
case object Id extends Permutation[Nothing]
case class Mapping[A](mappings: Map[A, A]) extends Permutation[A]

object Permutation {

  def id = Id

  // for creating permutations consisting of a single cycle, i.e. (1 2 3) instead of the mapping 1->2, 2->3, 3->1
  def cycle[A](vs: A*): Permutation[A] = {
    require(vs.size == vs.distinct.size)
    vs.toList match {
      case Nil => Id
      case a +: Seq() => Id
      case as => Mapping(as.sliding(2).map(l => (l.head, l.last)).toMap + (as.last -> as.head))
    }
  }

  // for creating permutations by explicitly defining the mapping
  def mapping[A](mappings: Map[A, A]): Permutation[A] = {
    require(mappings.keySet == mappings.values.toSet)
    if (mappings.size < 2) Id else Mapping[A](mappings)
  }

  implicit def pOps[A](p: Permutation[A]): PermutationOps[A] = new PermutationOps[A](p)

}

class PermutationOps[A](p: Permutation[A]) {

  import Permutation._
  
  // note that the operation is right-associative, so c *: b *: a is equivalent to (a.*:(b)).*:(c)
  def *:(p2: Permutation[A]): Permutation[A] = (p, p2) match {
    case (Id, f) => f
    case (f, Id) => f
    case (Mapping(m1), Mapping(m2)) => {
      val newMappings = (m2 ++ m1.map{ case (k,v) => (k, m2.getOrElse(v, v)) }).filter(v => v._1 != v._2)
      mapping(newMappings)
    }
  }

  def order: Int = {
    def loop(acc: Permutation[A], n: Int): Int = if (acc == Id) n else loop(p *: acc, n+1)
    loop(p, 1)
  }

  def inverse: Permutation[A] = ^(order - 1)

  def ^(power: Int): Permutation[A] = power match {
    case 0 => Id
    case n if n > 0 => p *: p.^(n-1)
    case n if n < 0 => p.inverse.^(-1 * n)
  }

  private def takeFirstDisjointCycle(m: Map[A, A], ord: Ordering[A]): (Seq[A], Map[A, A]) = {
    def loop(acc: Seq[A], m: Map[A, A]): (Seq[A], Map[A, A]) = {
      if (m(acc.last) == acc.head) (acc, m - acc.last) else loop(acc :+ m(acc.last), m - acc.last)
    }
    loop(Seq(m.keys.min(ord)), m)
  }

  def disjointCycles(implicit ord: Ordering[A]): Seq[Permutation[A]] = p match {
    case Id         => Seq()
    case Mapping(m) => {
      val (c, rm) = takeFirstDisjointCycle(m, ord)
      cycle(c:_*) +: mapping(rm).disjointCycles
    }
  }

  def show(implicit ord: Ordering[A]): String = p match {
    case Id         => ""
    case Mapping(m) => {
      val (c, rm) = takeFirstDisjointCycle(m, ord)
      c.mkString("(", " ", ")") + mapping(rm).show
    }
  }

}

import Permutation._

val a: Permutation[String] = cycle("A1", "A2", "A3") *: cycle("H1", "F2", "G3") *: cycle("F1", "G2", "H3") *: cycle("G1", "H2", "F3")

val b: Permutation[String] = cycle("B1", "B2", "B3") *: cycle("H1", "G2", "E3") *: cycle("G1", "E2", "H3") *: cycle("E1", "H2", "G3")

val c: Permutation[String] = cycle("C1", "C2", "C3") *: cycle("H1", "E2", "F3") *: cycle("E1", "F2", "H3") *: cycle("F1", "H2", "E3")

val d: Permutation[String] = cycle("D1", "D2", "D3") *: cycle("E1", "G2", "F3") *: cycle("F1", "E2", "G3") *: cycle("G1", "F2", "E3")

val e: Permutation[String] = cycle("E1", "E2", "E3") *: cycle("B1", "C2", "D3") *: cycle("C1", "D2", "B3") *: cycle("D1", "B2", "C3")

val f: Permutation[String] = cycle("F1", "F2", "F3") *: cycle("A1", "D2", "C3") *: cycle("D1", "C2", "A3") *: cycle("C1", "A2", "D3")

val g: Permutation[String] = cycle("G1", "G2", "G3") *: cycle("A1", "B2", "D3") *: cycle("D1", "A2", "B3") *: cycle("B1", "D2", "A3")

val h: Permutation[String] = cycle("H1", "H2", "H3") *: cycle("A1", "C2", "B3") *: cycle("B1", "A2", "C3") *: cycle("C1", "B2", "A3")