Skip to content

Instantly share code, notes, and snippets.

@micrypt
Created October 7, 2011 23:59
Show Gist options
  • Save micrypt/1271647 to your computer and use it in GitHub Desktop.
Save micrypt/1271647 to your computer and use it in GitHub Desktop.
Combinations - In essence: "The problem is one of turning a list of values, say, [A, B, C, D] into a list of pairs with itself, like so [[A,B], [A,C], [A,D], [B, C], [B,D], [C,D]]."
a = 'abcd'
comb=: 4 : 0
k=. i.>:d=.y-x
z=. (d$<i.0 0),<i.1 0
for. i.x do. z=. k ,.&.> ,&.>/\. >:&.> z end.
; z
)
(2 comb #a) { a
class PureCombinationsList[A](ls:List[A]){
def flatMapInnerlists[A,B](ls: List[A]=ls)(f: (List[A]) => List[B]): List[B] = ls match {
case Nil => Nil
case innerlist@(_ :: tail) => f(innerlist) ::: flatMapInnerlists(tail)(f)
}
def pureCombinations[A](n: Int, ls: List[A]=ls): List[List[A]] = {
if (n == 0) List(Nil)
else flatMapInnerlists(ls) { sl =>
pureCombinations(n - 1, sl.tail) map {sl.head :: _}
}
}
}
implicit def toPureCombinationsList[A](seq:List[A]) = new PureCombinationsList(seq)
//List("a","b","c","d") pureCombinations(2)
//List[List[java.lang.String]] = List(List(a, b), List(a, c), List(a, d), List(b, c), List(b, d), List(c, d))
// Alternate solution by XxXX
def pair(l : List[String]): List[Tuple2[String, String]] = l.size match {
case 1 => Nil
case _ => l.tail.flatMap { e => List((l.head, e)) } ++ pair(l.tail)
}
@ikennaokpala
Copy link

this is awesome.. nice you shared it..

@micrypt
Copy link
Author

micrypt commented Oct 8, 2011

It's a shame the Scala stdlib combinations function isn't pure, otherwise it'd be so much more succinct > List("a","b","c","d") combinations(2) toList

@ikennaokpala
Copy link

yeah i feel your point but you can submit a patch..

@micrypt
Copy link
Author

micrypt commented Oct 8, 2011

True. I'll see about generalizing this.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment