scala - 我的组合函数返回一个空列表

Question

我正在研究 S-99: Ninety-Nine Scala Problems并且已经卡在了第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))

但是，我的组合返回一个空列表。任何想法？也非常欢迎其他带有解释的解决方案。谢谢

编辑:问题的描述

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), ...

Answer 1

正如 Noah 所指出的，我的问题是 for 的空列表不会产生。然而，Noah 建议的绕过 hacky 的工作是错误的。它向每个递归步骤的结果添加一个空列表。无论如何，这是我的最终解决方案。我将基本案例更改为“案例(1，xs)”。 (n 匹配 1)

def combinations[T](n: Int, ls: List[T]): List[List[T]] = (n, ls) match {
case (1, xs) =>  xs.map(List(_))
case (n, xs) => {
  val tails = allTails(xs).reverse
  for {
    y :: xss <- allTails(xs).reverse
    ys <- combinations((n - 1), xss)
  } yield y :: ys
}
}
//combinations(3, List(1, 2, 3, 4))
//List(List(1, 2, 3), List(1, 2, 4), List(1, 3, 4), List(2, 3, 4))
//combinations(2, List(0, 1, 2, 3))
//List(List(0, 1), List(0, 2), List(0, 3), List(1, 2), List(1, 3), List(2, 3))

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)) 
//List(List(3), List(2, 3), List(1, 2, 3), List(0, 1, 2, 3))