combinator.scala

// combinations without repetition
//
//
//       n!
//   ----------
//   r!(n - r)!
//
//   n = number of elements to choose from
//   r = how many we choose
//

def combinator[A](n: Int, list: List[A], acc: List[A]): List[List[A]] = {
  if (n == 0)
    List(acc.reverse)
  else if (list == Nil)
    List()
  else
    combinator(n - 1, list.tail, list.head :: acc) ::: combinator(n, list.tail, acc)
}

combinator(4, List(1, 2, 3, 4, 5), List()).foreach(println)

// List(1, 2, 3, 4)
// List(1, 2, 3, 5)
// List(1, 2, 4, 5)
// List(1, 3, 4, 5)
// List(2, 3, 4, 5)

combinator(4, List("A", "B", "C", "D", "E"), List()).foreach(println)

// List(A, B, C, D)
// List(A, B, C, E)
// List(A, B, D, E)
// List(A, C, D, E)
// List(B, C, D, E)