在Scala中列出带有重复的组合 [英] Listing combinations WITH repetitions in Scala

问题描述

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

Trying to learn a bit of Scala and ran into this problem. I found a solution for all combinations without repetions here and I somewhat understand the idea behind it but some of the syntax is messing me up. I also don't think the solution is appropriate for a case WITH repetitions. I was wondering if anyone could suggest a bit of code that I could work from. I have plenty of material on combinatorics and understand the problem and iterative solutions to it, I am just looking for the scala-y way of doing it.

谢谢

推荐答案

我现在了解您的问题。我认为实现所需目标的最简单方法是执行以下操作：

I understand your question now. I think the easiest way to achieve what you want is to do the following:

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 在列表中。

The comb method just calls mycomb with duplicates removed from the input list. Removing the duplicates means it is then easier to test later whether two elements are 'the same'. The only change I have made to your mycomb method is that when the method is being called recursively I strip off the elements which appear before el in the list. This is to stop there being duplicates in the output.

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

这篇关于在Scala中列出带有重复的组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！