Skip to content

Instantly share code, notes, and snippets.

@DarkDimius
Created November 7, 2012 22:15
Show Gist options
  • Save DarkDimius/4034869 to your computer and use it in GitHub Desktop.
Save DarkDimius/4034869 to your computer and use it in GitHub Desktop.
First Homework
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(_))
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment