Skip to content

Instantly share code, notes, and snippets.

@vkostyukov
Created February 15, 2014 08:08
Show Gist options
  • Save vkostyukov/9015987 to your computer and use it in GitHub Desktop.
Save vkostyukov/9015987 to your computer and use it in GitHub Desktop.
/**
* A tiny class that extends a list with four combinatorial operations:
* ''combinations'', ''subsets'', ''permutations'', ''variations''.
*
* You can find all the ideas behind this code at blog-post:
*
* http://vkostyukov.ru/posts/combinatorial-algorithms-in-scala/
*
* How to use this class.
*
* import CombinatorialOps._
* val v = List(1, 2, 3).xvariations(2)
*
* The following functions are available:
*
* - xcombinations(n) -- generates n-combinations
* - xsubsets -- generates all subsets
* - xvariations(n) -- generates n-variations
* - xpermutations -- generates all permutations
*
*/
object CombinatorialOps {
implicit class CombinatorialList[A](l: List[A]) {
/**
* A pre-calculated size of given list.
*/
val xsize = l.size
/**
* Generates the combinations of this list with given length 'n'. The order
* doesn't matter.
*
* The total number of k-combinations on n-length set might be calculated
* as follows:
*
* C_k,n = n!/k!(n - k)!
*
* Time - O(C_k,n)
* Space - O(C_k,n)
*/
def xcombinations(n: Int): List[List[A]] =
if (n > xsize) Nil
else l match {
case _ :: _ if n == 1 => l.map(List(_))
case hd :: tl => tl.xcombinations(n - 1).map(hd :: _) ::: tl.xcombinations(n)
case _ => Nil
}
/**
* Generates all the subsets of this list. The order doesn't matter.
*
* The total number of subsets might be obtained from variations formula:
*
* S_n = sum(i=1..n) {C_i,n} = 2 ** n
* Time - O(S_n)
* Space - O(S_n)
*/
def xsubsets: List[List[A]] =
(2 to xsize).foldLeft(l.xcombinations(1))((a, i) => l.xcombinations(i) ::: a)
/**
* Generates the variations of this list with given length 'n'. The order
* does matter.
*
* The total number of variations might be calculated as follows:
*
* V_k,n = n!/(n - k)!
*
* Time - O(V_k,n)
* Space - O(V_k,n)
*/
def xvariations(n: Int): List[List[A]] = {
def mixmany(x: A, ll: List[List[A]]): List[List[A]] = ll match {
case hd :: tl => foldone(x, hd) ::: mixmany(x, tl)
case _ => Nil
}
def foldone(x: A, ll: List[A]): List[List[A]] =
(1 to ll.length).foldLeft(List(x :: ll))((a, i) => (mixone(i, x, ll)) :: a)
def mixone(i: Int, x: A, ll: List[A]): List[A] =
ll.slice(0, i) ::: (x :: ll.slice(i, ll.length))
if (n > xsize) Nil
else l match {
case _ :: _ if n == 1 => l.map(List(_))
case hd :: tl => mixmany(hd, tl.xvariations(n - 1)) ::: tl.xvariations(n)
case _ => Nil
}
}
/**
* Generates all permutations of this list. The order does matter.
*
* The total number of permutations might be calculated as follows:
*
* P_n = V_n,n = n!
*
* Time - O(n!)
* Space - O(n!)
*/
def xpermutations: List[List[A]] = xvariations(xsize)
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment