scala - 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)

标签： scalacombinationscombinatorics

Answer 1

案例太多，不必要的combinations2繁琐subList。

---

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

• 您不包含a1在子集中。然后你必须k从剩余的{a2, ..., aN}.
• 您包含a1在子集中。然后你必须从中选择k-1元素{a2, ..., aN}，并添加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)