scala - 在Scala中列出带有重复的组合

Question

尝试学习一些Scala并遇到了这个问题。我找到了没有重复的所有组合的解决方案here，我对它背后的想法有些了解，但某些语法使我感到困惑。我也不认为该解决方案适用于重复的情况。我想知道是否有人可以建议我可以使用的一些代码。我有很多关于组合学的资料，并且了解问题及其迭代解决方案，我只是在寻找可扩展的方法。

谢谢

Answer 1

我现在明白你的问题。我认为实现所需目标的最简单方法是执行以下操作:

def mycomb[T](n: Int, l: List[T]): List[List[T]] =
  n match {
    case 0 => List(List())
    case _ => for(el <- l;
              sl <- mycomb(n-1, l dropWhile { _ != el } ))
              yield el :: sl
}

def comb[T](n: Int, l: List[T]): List[List[T]] = mycomb(n, l.removeDuplicates)

comb方法仅调用 mycomb，并将重复项从输入列表中删除。删除重复项意味着以后可以更轻松地测试两个元素是否“相同”。我对 mycomb方法所做的唯一更改是，以递归方式调用该方法时，我剥离了列表中 el之前出现的元素。这是为了防止输出中出现重复项。

> comb(3, List(1,2,3))
> List[List[Int]] = List(
    List(1, 1, 1), List(1, 1, 2), List(1, 1, 3), List(1, 2, 2), 
    List(1, 2, 3), List(1, 3, 3), List(2, 2, 2), List(2, 2, 3), 
    List(2, 3, 3), List(3, 3, 3))

> comb(6, List(1,2,1,2,1,2,1,2,1,2))
> List[List[Int]] = List(
    List(1, 1, 1, 1, 1, 1), List(1, 1, 1, 1, 1, 2), List(1, 1, 1, 1, 2, 2), 
    List(1, 1, 1, 2, 2, 2), List(1, 1, 2, 2, 2, 2), List(1, 2, 2, 2, 2, 2), 
    List(2, 2, 2, 2, 2, 2))