First Homework

hw.scala

 def gcd(a: Int, b: Int) {
    if (a == 0) {
      (0, 1, b)
    }
    else {
      val (d, x1, y1) = gcd(b % a, a)
      val x = y1 - (b / a) * x1
      val y = x1
      (x, y, d)
    }
  }

  def pow(a: Double, n: Int) = {
    val res = 1.0
    while (n > 0) {
      if (n & 1)
        res *= a
      a *= a
      n >>= 1
    }
    res
  }

  type BinaryOp=IndexedSeq[IndexedSeq[Int]]

  def commutative(op:BinaryOp) = {

      op.zipWithIndex.forall{
        case (line,row)=>
          line.zipWithIndex.forall{
            case(value,col) =>
            op(row)(col)==value
          }
      }
  }

  def associative(op:BinaryOp) = {
    val size=op.size
    op.view.zipWithIndex.forall{
      case (line,first)=>
        line.view.zipWithIndex.forall{
          case(value,second) =>
            (1 to size).forall{ third=>
            op(value)(third)==op(first)(op(second)(third))
            }
        }
    }
  }

  def monoid(op:BinaryOp):Option[Int] = {
    op.view.zipWithIndex.find{
      case (line,row) => {
            line.view.zipWithIndex.forall{
              case (value,col) =>
              value==col
            }
      }
    }.map(_._2)
  }

  def group(op:BinaryOp) = {
    monoid(op) match {
      case Some(identity) =>
        def existsInverse(elem:Int) = {
           op(elem).contains(identity)
        }
        val groupSize=op.size
        (1 to groupSize).forall(existsInverse(_))&associative(op)
      case None=>
        false
    }
  }


    def isomorphic(op1:BinaryOp, op2:BinaryOp) = {
        op.permutations.find{_==op2}.isDefined
    }

    def allSubMonoids(op:BinaryOp, size:Int) = {
      op.combinations(size).filter(monoid(_))
    }

    /**
     * i assume that a semigroup is an algebraic structure consisting of a set together with an associative binary operation
     */

    def allSubSemigroups(op:BinaryOp, size:Int) = {
      op.combinations(size).filter(associative(_))
    }