Skip to content

Instantly share code, notes, and snippets.

@johnynek

johnynek/3 element semilattices

Created November 9, 2015 07:58
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save johnynek/f5b6635f99e568004373 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save johnynek/f5b6635f99e568004373 to your computer and use it in GitHub Desktop.
Download ZIP
Brute force enumeration of all semilattices (and commutative semigroups) of finite size
Raw
3 element semilattices
There are 9 semilattices on [0,1,2]:
0 1 2
- - -
0| 0 0 0
1| 0 1 0
2| 0 0 2
-----------------------
0 1 2
- - -
0| 0 0 0
1| 0 1 1
2| 0 1 2
-----------------------
0 1 2
- - -
0| 0 1 0
1| 1 1 1
2| 0 1 2
-----------------------
0 1 2
- - -
0| 0 1 1
1| 1 1 1
2| 1 1 2
-----------------------
0 1 2
- - -
0| 0 1 2
1| 1 1 1
2| 2 1 2
-----------------------
0 1 2
- - -
0| 0 0 0
1| 0 1 2
2| 0 2 2
-----------------------
0 1 2
- - -
0| 0 0 2
1| 0 1 2
2| 2 2 2
-----------------------
0 1 2
- - -
0| 0 1 2
1| 1 1 2
2| 2 2 2
-----------------------
0 1 2
- - -
0| 0 2 2
1| 2 1 2
2| 2 2 2
-----------------------
Raw
4 element semilattices
There are 76 semilattices on [0,1,2,3]:
0 1 2 3
- - - -
0| 0 0 0 0
1| 0 1 0 0
2| 0 0 2 0
3| 0 0 0 3
-----------------------
0 1 2 3
- - - -
0| 0 0 0 0
1| 0 1 1 0
2| 0 1 2 0
3| 0 0 0 3
-----------------------
0 1 2 3
- - - -
0| 0 0 0 0
1| 0 1 2 0
2| 0 2 2 0
3| 0 0 0 3
-----------------------
0 1 2 3
- - - -
0| 0 0 0 0
1| 0 1 0 1
2| 0 0 2 0
3| 0 1 0 3
-----------------------
0 1 2 3
- - - -
0| 0 1 0 0
1| 1 1 1 1
2| 0 1 2 0
3| 0 1 0 3
-----------------------
0 1 2 3
- - - -
0| 0 0 0 0
1| 0 1 0 3
2| 0 0 2 0
3| 0 3 0 3
-----------------------
0 1 2 3
- - - -
0| 0 0 0 0
1| 0 1 2 3
2| 0 2 2 0
3| 0 3 0 3
-----------------------
0 1 2 3
- - - -
0| 0 0 0 0
1| 0 1 1 1
2| 0 1 2 1
3| 0 1 1 3
-----------------------
0 1 2 3
- - - -
0| 0 1 1 0
1| 1 1 1 1
2| 1 1 2 1
3| 0 1 1 3
-----------------------
0 1 2 3
- - - -
0| 0 1 0 1
1| 1 1 1 1
2| 0 1 2 1
3| 1 1 1 3
-----------------------
0 1 2 3
- - - -
0| 0 1 1 1
1| 1 1 1 1
2| 1 1 2 1
3| 1 1 1 3
-----------------------
0 1 2 3
- - - -
0| 0 1 2 1
1| 1 1 1 1
2| 2 1 2 1
3| 1 1 1 3
-----------------------
0 1 2 3
- - - -
0| 0 1 1 3
1| 1 1 1 1
2| 1 1 2 1
3| 3 1 1 3
-----------------------
0 1 2 3
- - - -
0| 0 1 2 3
1| 1 1 1 1
2| 2 1 2 1
3| 3 1 1 3
-----------------------
0 1 2 3
- - - -
0| 0 0 0 0
1| 0 1 0 0
2| 0 0 2 2
3| 0 0 2 3
-----------------------
0 1 2 3
- - - -
0| 0 0 2 0
1| 0 1 2 0
2| 2 2 2 2
3| 0 0 2 3
-----------------------
0 1 2 3
- - - -
0| 0 0 0 0
1| 0 1 0 1
2| 0 0 2 2
3| 0 1 2 3
-----------------------
0 1 2 3
- - - -
0| 0 0 0 0
1| 0 1 1 1
2| 0 1 2 2
3| 0 1 2 3
-----------------------
0 1 2 3
- - - -
0| 0 1 0 0
1| 1 1 1 1
2| 0 1 2 2
3| 0 1 2 3
-----------------------
0 1 2 3
- - - -
0| 0 1 1 0
1| 1 1 1 1
2| 1 1 2 2
3| 0 1 2 3
-----------------------
0 1 2 3
- - - -
0| 0 1 2 0
1| 1 1 1 1
2| 2 1 2 2
3| 0 1 2 3
-----------------------
0 1 2 3
- - - -
0| 0 1 1 1
1| 1 1 1 1
2| 1 1 2 2
3| 1 1 2 3
-----------------------
0 1 2 3
- - - -
0| 0 1 2 2
1| 1 1 1 1
2| 2 1 2 2
3| 2 1 2 3
-----------------------
0 1 2 3
- - - -
0| 0 1 2 3
1| 1 1 1 1
2| 2 1 2 2
3| 3 1 2 3
-----------------------
0 1 2 3
- - - -
0| 0 0 0 0
1| 0 1 2 1
2| 0 2 2 2
3| 0 1 2 3
-----------------------
0 1 2 3
- - - -
0| 0 0 2 0
1| 0 1 2 1
2| 2 2 2 2
3| 0 1 2 3
-----------------------
0 1 2 3
- - - -
0| 0 1 2 0
1| 1 1 2 1
2| 2 2 2 2
3| 0 1 2 3
-----------------------
0 1 2 3
- - - -
0| 0 2 2 0
1| 2 1 2 1
2| 2 2 2 2
3| 0 1 2 3
-----------------------
0 1 2 3
- - - -
0| 0 1 2 1
1| 1 1 2 1
2| 2 2 2 2
3| 1 1 2 3
-----------------------
0 1 2 3
- - - -
0| 0 2 2 2
1| 2 1 2 1
2| 2 2 2 2
3| 2 1 2 3
-----------------------
0 1 2 3
- - - -
0| 0 1 2 3
1| 1 1 2 1
2| 2 2 2 2
3| 3 1 2 3
-----------------------
0 1 2 3
- - - -
0| 0 0 0 0
1| 0 1 2 2
2| 0 2 2 2
3| 0 2 2 3
-----------------------
0 1 2 3
- - - -
0| 0 2 2 0
1| 2 1 2 2
2| 2 2 2 2
3| 0 2 2 3
-----------------------
0 1 2 3
- - - -
0| 0 0 2 2
1| 0 1 2 2
2| 2 2 2 2
3| 2 2 2 3
-----------------------
0 1 2 3
- - - -
0| 0 1 2 2
1| 1 1 2 2
2| 2 2 2 2
3| 2 2 2 3
-----------------------
0 1 2 3
- - - -
0| 0 2 2 2
1| 2 1 2 2
2| 2 2 2 2
3| 2 2 2 3
-----------------------
0 1 2 3
- - - -
0| 0 1 2 3
1| 1 1 2 2
2| 2 2 2 2
3| 3 2 2 3
-----------------------
0 1 2 3
- - - -
0| 0 2 2 3
1| 2 1 2 2
2| 2 2 2 2
3| 3 2 2 3
-----------------------
0 1 2 3
- - - -
0| 0 0 0 0
1| 0 1 2 3
2| 0 2 2 2
3| 0 3 2 3
-----------------------
0 1 2 3
- - - -
0| 0 0 2 0
1| 0 1 2 3
2| 2 2 2 2
3| 0 3 2 3
-----------------------
0 1 2 3
- - - -
0| 0 0 2 2
1| 0 1 2 3
2| 2 2 2 2
3| 2 3 2 3
-----------------------
0 1 2 3
- - - -
0| 0 2 2 2
1| 2 1 2 3
2| 2 2 2 2
3| 2 3 2 3
-----------------------
0 1 2 3
- - - -
0| 0 0 2 3
1| 0 1 2 3
2| 2 2 2 2
3| 3 3 2 3
-----------------------
0 1 2 3
- - - -
0| 0 1 2 3
1| 1 1 2 3
2| 2 2 2 2
3| 3 3 2 3
-----------------------
0 1 2 3
- - - -
0| 0 3 2 3
1| 3 1 2 3
2| 2 2 2 2
3| 3 3 2 3
-----------------------
0 1 2 3
- - - -
0| 0 0 0 0
1| 0 1 0 0
2| 0 0 2 3
3| 0 0 3 3
-----------------------
0 1 2 3
- - - -
0| 0 0 0 0
1| 0 1 1 0
2| 0 1 2 3
3| 0 0 3 3
-----------------------
0 1 2 3
- - - -
0| 0 0 0 0
1| 0 1 1 1
2| 0 1 2 3
3| 0 1 3 3
-----------------------
0 1 2 3
- - - -
0| 0 1 0 0
1| 1 1 1 1
2| 0 1 2 3
3| 0 1 3 3
-----------------------
0 1 2 3
- - - -
0| 0 1 0 1
1| 1 1 1 1
2| 0 1 2 3
3| 1 1 3 3
-----------------------
0 1 2 3
- - - -
0| 0 1 1 1
1| 1 1 1 1
2| 1 1 2 3
3| 1 1 3 3
-----------------------
0 1 2 3
- - - -
0| 0 1 0 3
1| 1 1 1 1
2| 0 1 2 3
3| 3 1 3 3
-----------------------
0 1 2 3
- - - -
0| 0 1 2 3
1| 1 1 1 1
2| 2 1 2 3
3| 3 1 3 3
-----------------------
0 1 2 3
- - - -
0| 0 1 3 3
1| 1 1 1 1
2| 3 1 2 3
3| 3 1 3 3
-----------------------
0 1 2 3
- - - -
0| 0 0 0 3
1| 0 1 0 3
2| 0 0 2 3
3| 3 3 3 3
-----------------------
0 1 2 3
- - - -
0| 0 0 0 0
1| 0 1 1 3
2| 0 1 2 3
3| 0 3 3 3
-----------------------
0 1 2 3
- - - -
0| 0 0 0 3
1| 0 1 1 3
2| 0 1 2 3
3| 3 3 3 3
-----------------------
0 1 2 3
- - - -
0| 0 1 0 3
1| 1 1 1 3
2| 0 1 2 3
3| 3 3 3 3
-----------------------
0 1 2 3
- - - -
0| 0 3 0 3
1| 3 1 1 3
2| 0 1 2 3
3| 3 3 3 3
-----------------------
0 1 2 3
- - - -
0| 0 1 1 3
1| 1 1 1 3
2| 1 1 2 3
3| 3 3 3 3
-----------------------
0 1 2 3
- - - -
0| 0 1 2 3
1| 1 1 1 3
2| 2 1 2 3
3| 3 3 3 3
-----------------------
0 1 2 3
- - - -
0| 0 3 3 3
1| 3 1 1 3
2| 3 1 2 3
3| 3 3 3 3
-----------------------
0 1 2 3
- - - -
0| 0 0 0 0
1| 0 1 2 3
2| 0 2 2 3
3| 0 3 3 3
-----------------------
0 1 2 3
- - - -
0| 0 0 0 3
1| 0 1 2 3
2| 0 2 2 3
3| 3 3 3 3
-----------------------
0 1 2 3
- - - -
0| 0 0 2 3
1| 0 1 2 3
2| 2 2 2 3
3| 3 3 3 3
-----------------------
0 1 2 3
- - - -
0| 0 1 2 3
1| 1 1 2 3
2| 2 2 2 3
3| 3 3 3 3
-----------------------
0 1 2 3
- - - -
0| 0 2 2 3
1| 2 1 2 3
2| 2 2 2 3
3| 3 3 3 3
-----------------------
0 1 2 3
- - - -
0| 0 0 3 3
1| 0 1 2 3
2| 3 2 2 3
3| 3 3 3 3
-----------------------
0 1 2 3
- - - -
0| 0 3 3 3
1| 3 1 2 3
2| 3 2 2 3
3| 3 3 3 3
-----------------------
0 1 2 3
- - - -
0| 0 0 0 0
1| 0 1 3 3
2| 0 3 2 3
3| 0 3 3 3
-----------------------
0 1 2 3
- - - -
0| 0 3 0 3
1| 3 1 3 3
2| 0 3 2 3
3| 3 3 3 3
-----------------------
0 1 2 3
- - - -
0| 0 1 2 3
1| 1 1 3 3
2| 2 3 2 3
3| 3 3 3 3
-----------------------
0 1 2 3
- - - -
0| 0 3 2 3
1| 3 1 3 3
2| 2 3 2 3
3| 3 3 3 3
-----------------------
0 1 2 3
- - - -
0| 0 0 3 3
1| 0 1 3 3
2| 3 3 2 3
3| 3 3 3 3
-----------------------
0 1 2 3
- - - -
0| 0 1 3 3
1| 1 1 3 3
2| 3 3 2 3
3| 3 3 3 3
-----------------------
0 1 2 3
- - - -
0| 0 3 3 3
1| 3 1 3 3
2| 3 3 2 3
3| 3 3 3 3
-----------------------
Raw
semilattice.scala
object Lattices {
trait BinaryOp {
def size: Int
def apply(a: Int, b: Int): Int
override def toString: String =
(0 until size).mkString("\t", "\t", "") + "\n" +
(0 until size).map(_ => "-").mkString("\t", "\t", "") + "\n" +
((0 until size).map { a =>
s"$a|\t" + (0 until size).map { b => apply(a, b) }.mkString("\t")
}.mkString("\n"))
}
def isAssociative(size: Int, op: BinaryOp): Boolean = (for {
a <- (0 until size).iterator
b <- (0 until size).iterator
c <- (0 until size).iterator
} yield (a, b, c)).forall { case (a, b, c) => op(op(a, b), c) == op(a, op(b, c)) }
def isCommutative(size: Int, op: BinaryOp): Boolean = (for {
a <- (0 until size).iterator
b <- (0 until size).iterator
} yield (a, b)).forall { case (a, b) => op(a, b) == op(b, a) }
def isIdempotent(size: Int, op: BinaryOp): Boolean =
(0 until size).forall { a => op(a, a) == a }
def next(size: Int, v: List[Int]): Option[List[Int]] = v match {
case Nil => None
case h :: tail if ((h + 1) < size) => Some((h + 1) :: tail)
case h :: tail => next(size, tail).map(0 :: _)
}
case class BinaryOpFrom(size: Int, v: List[Int]) extends BinaryOp {
lazy val vec = v.toVector
def apply(a: Int, b: Int) = vec(a * size + b)
}
def allTables(elements: Int, tableSize: Int): Stream[List[Int]] = {
def from(v: List[Int]): Stream[List[Int]] = v #:: (next(elements, v) match {
case None => Stream.empty
case Some(v1) => from(v1)
})
from(List.fill(tableSize)(0))
}
/**
* All possible binary operations on a certain size input
* This is really inefficient, especially for semilattices
*/
def allOps(size: Int): Stream[BinaryOp] =
allTables(size, size * size).map(BinaryOpFrom(size, _))
def allSemigroups(size: Int): Stream[BinaryOp] =
allOps(size).filter(isAssociative(size, _))
def allCommutativeSemigroups(size: Int): Stream[BinaryOp] = {
/**
* commutative operations are symmetrical
*/
case class Commutative(size: Int, v: List[Int]) extends BinaryOp {
lazy val vec = v.toVector
def apply(a: Int, b: Int) = {
if (a > b) apply(b, a)
else {
// store first n, (n - 1), (n - 2), etc...
val (nextIdx, offset) = (0 until a).foldLeft((0, 0)) { case ((idx, sum), _) =>
(idx + 1, sum + (size - idx))
}
vec(offset + b - nextIdx)
}
}
}
allTables(size, size * (size + 1)/2).map(Commutative(size, _))
.filter(isAssociative(size, _))
}
def allSemilattices(size: Int): Stream[BinaryOp] = {
/**
* semilattices are symmetrical and have identity on the diagonal
*/
case class CommutativeIdem(size: Int, v: List[Int]) extends BinaryOp {
lazy val vec = v.toVector
def apply(a: Int, b: Int) = {
if (a > b) apply(b, a)
else if (a == b) a
else {
// store first (n - 1), (n - 2), etc...
val (nextIdx, offset) = (0 until a).foldLeft((1, 0)) { case ((idx, sum), _) =>
(idx + 1, sum + (size - idx))
}
vec(offset + b - nextIdx)
}
}
}
allTables(size, size * (size - 1)/2).map(CommutativeIdem(size, _))
.filter(isAssociative(size, _))
}
}
val sl4 = Lattices.allSemilattices(4)
println(s"There are ${sl4.size} semilattices on [0,1,2,3]:")
sl4.foreach { sg =>
println(sg)
println("-----------------------")
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment