列出Scala中重复的组合

Question

试图学习一点Scala并遇到这个问题.我发现没有repetions对所有组合的解决方案在这里,我有所了解的想法背后,但一些语法是搞乱了我.我也不认为该解决方案适用于重复的情况.我想知道是否有人可以建议我可以使用的一些代码.我有很多关于组合学的材料,并且理解问题和迭代解决方案,我只是在寻找scala-y的方法.

谢谢

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

Answer 2

同时,组合已成为scala集合的组成部分:

scala> val li = List (1, 1, 0, 0) 
li: List[Int] = List(1, 1, 0, 0)

scala> li.combinations (2) .toList
res210: List[List[Int]] = List(List(1, 1), List(1, 0), List(0, 0))

正如我们所看到的,它不允许重复,但允许它们很简单,但是:组合集合中的每个元素(0到li.size-1)并映射到列表中的元素:

scala> (0 to li.length-1).combinations (2).toList .map (v=>(li(v(0)), li(v(1))))
res214: List[(Int, Int)] = List((1,1), (1,0), (1,0), (1,0), (1,0), (0,0))