我正在研究S-99:九十九个 Scala 问题并且已经停留在问题 26 上。 生成从列表的 N 个元素中选择的 K 个不同对象的组合。 浪费了几个小时后,我决定看一下用 Haskell 编写的解决方案:
combinations :: Int -> [a] -> [[a]]
combinations 0 _ = [ [] ]
combinations n xs = [ y:ys | y:xs' <- tails xs
, ys <- combinations (n-1) xs']
它看起来很简单,所以我决定翻译成 Scala。(我知道这是作弊。)这是我到目前为止得到的:
def combinations[T](n: Int, ls: List[T]): List[List[T]] = (n, ls) match {
case (0, _) => List[List[T]]()
case (n, xs) => {
for {
y :: xss <- allTails(xs).reverse
ys <- combinations((n - 1), xss)
} yield y :: ys
}
}
我的辅助功能:
def allTails[T](ls: List[T]): List[List[T]] = {
ls./:(0, List[List[T]]())((acc, c) => {
(acc._1 + 1, ls.drop(acc._1) :: acc._2)
})._2 }
allTails(List(0, 1, 2, 3)).reverse
//> res1: List[List[Int]] = List(List(0, 1, 2, 3), List(1, 2, 3), List(2, 3), List(3))
但是,我的组合返回一个空列表。任何的想法?其他带有解释的解决方案也非常受欢迎。谢谢
编辑:问题的描述
生成从列表的 N 个元素中选择的 K 个不同对象的组合。从 12 个人中选出一个 3 人的委员会有几种方法?我们都知道有 C(12,3) = 220 种可能性(C(N,K) 表示众所周知的二项式系数)。对于纯数学家来说,这个结果可能很棒。但我们想真正产生所有的可能性。
示例: scala> combination(3, List('a, 'b, 'c, 'd, 'e, 'f)) res0: List[List[Symbol]] = List(List('a, 'b, ' c), 列表('a, 'b, 'd), 列表('a, 'b, 'e), ...