Scala 自定义组合函数

Question

我想在scala中实现一个组合函数，我的代码如下：

def combination[A](n: Int, ls: List[A]): List[List[A]] ={
    (n, ls) match{
        case (_, Nil) => List(Nil)
        case (1, _) => ls.map(List(_))
        case (_, _) if n > ls.size => List.empty
        case _ => ls.flatMap(x => combination(n - 1, subList(x, ls)).map(x :: _))
      }
  }
def subList[A](e: A, in: List[A]) = in.takeRight(in.size - in.indexOf(e) - 1)

但结果不是我所期望的。当我打电话给 combination(3, List('a, 'b, 'c, 'd, 'e, 'f) 时。它会给我那些带有一个或两个元素的结果，比如 List('d, 'f), List('f) 等等。谁能帮我找到问题所在？谢谢

更新：正确的版本是

def combination[A](n: Int, ls: List[A]): List[List[A]] ={
    (n, ls) match{
        case (_, Nil) => Nil
        case (1, _) => ls.map(List(_))
        case (_, _) if n > ls.size => Nil
        case _ => ls.flatMap(x => combination(n - 1, subList(x, ls)).map(x :: _))
      }
  }
def subList[A](e: A, in: List[A]) = in.takeRight(in.size - in.indexOf(e) - 1)

Answer 1

在最后一种情况下，您正在呼叫 combination2。如果您更改为 combination（具有 subList 的合理定义），它会起作用。我想这是中间版本剩下的东西。

Answer 2

案例太多，没必要复杂combinations2和subList。

回想一下 combinations 是如何定义的。如果你有一个集合 {a1, ..., aN}，并且你想从这个集合中 select k 个元素，那么你基本上可以做两个事情：

您没有将 a1 包含到子集中。那么你必须从剩余的{a2, ..., aN}.

k

您将 a1 包含到子集中。然后你必须从 {a2, ..., aN} 中提取 select k-1 个元素，并将 a0 添加到那些 k-1 个元素中。

这就是公式

C(N, k) =         C(N - 1, k) + C(N - 1, k - 1)

来自.

翻译成代码，就是这样：

def comb[A](ls: List[A], k: Int): List[List[A]] = {
  if (k == 0) List(Nil)
  else ls match {
    case Nil => List()
    case h :: t => comb(t, k) ++ comb(t, k - 1).map(h :: _)
  }
}

示例：

comb(List('a, 'b, 'c, 'd, 'e), 3) foreach println

给出：

List('c, 'd, 'e)
List('b, 'd, 'e)
List('b, 'c, 'e)
List('b, 'c, 'd)
List('a, 'd, 'e)
List('a, 'c, 'e)
List('a, 'c, 'd)
List('a, 'b, 'e)
List('a, 'b, 'd)
List('a, 'b, 'c)

Answer 3

有一种更简单的方法可以做到这一点

def comb[A](n: Int, ls:List[A]): List[List[A]] = {
  if(ls.isEmpty) List(Nil)
  else ls.toSet[A].subsets.map(_.toList).filter(_.length == n).toList
}

Scala fiddle

Scala 自定义组合函数

self defined combination function in Scala

combinations

scala

combinatorics