sublist@を使う
// P26 (**) Generate the combinations of K distinct objects chosen from the N // elements of a list. // In how many ways can a committee of 3 be chosen from a group of 12 // people? We all know that there are C(12,3) = 220 possibilities (C(N,K) // denotes the well-known binomial coefficient). For pure mathematicians, // this result may be great. But we want to really generate all the possibilities. // // Example: // scala> combinations(3, List('a, 'b, 'c, 'd, 'e, 'f)) // res0: List[List[Symbol]] = List(List('a, 'b, 'c), List('a, 'b, 'd), List('a, 'b, 'e), ...
object P26 { def combinations[T](n: Int, l: List[T]): List[List[T]] = { // flatMapSublists is like list.flatMap, but instead of passing each element // to the function, it passes successive sublists of L. def flatMapSublists[U](l: List[T], f: (List[T]) => List[U]): List[U] = l match { case Nil => Nil case sublist@(_ :: tail) => f(sublist) ::: flatMapSublists(tail, f) } if (n == 0) List(Nil) else flatMapSublists(l, (sl) => combinations(n - 1, sl.tail).map((c) => sl.head :: c)) } }