10

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

谢谢

4

7 回答 7

8

我现在明白你的问题了。我认为实现您想要的最简单的方法是执行以下操作:

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))
于 2009-07-07T08:17:36.403 回答
7

同时,组合已成为 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))
于 2012-06-18T06:15:39.293 回答
1

这个问题在其中一个答案中被改写了——我希望问题本身也能得到编辑。其他人回答了正确的问题。如果有人发现它有用,我将把该代码留在下面。

确实,该解决方案令人困惑。没有重复的“组合”称为排列。它可以是这样的:

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

如果不能保证输入列表包含唯一元素,如另一个答案中所建议的,则可能会更困难一些。我们只需要删除第一个元素,而不是删除所有元素的过滤器。

def perm[T](n: Int, l: List[T]): List[List[T]] = {
  def perm1[T](n: Int, l: List[T]): List[List[T]] =
    n match {
      case 0 => List(List())
      case _ => for(el <- l;
                    (hd, tl) = l span (_ != el);
                    sl <- perm(n-1, hd ::: tl.tail))
                yield el :: sl
    }
  perm1(n, l).removeDuplicates
}

只是一点解释。在 for 中,我们获取列表的每个元素,并返回由它组成的列表,然后是列表中除所选元素之外的所有元素的排列。

例如,如果我们取 List(1,2,3),我们将组成由 1 和 perm(List(2,3))、2 和 perm(List(1,3)) 以及 3 和 perm(列表(1,2))。

由于我们正在执行任意大小的排列,因此我们会跟踪每个子排列的长度。如果子排列的大小为 0,重要的是我们返回一个包含空列表的列表。请注意,这不是一个空列表!如果我们在 case 0 中返回 Nil,调用 perm 中将没有元素 for sl,整个“for”将产生 Nil。这样,sl 将被赋值为 Nil,我们将组成一个列表 el :: Nil,产生 List(el)。

不过,我正在考虑最初的问题,我将在此处发布我的解决方案以供参考。如果您的意思是由于输入中的元素重复而导致答案中没有重复的元素,只需添加一个 removeDuplicates ,如下所示。

def comb[T](n: Int, l: List[T]): List[List[T]] =
n match {
  case 0 => List(List())
  case _ => for(i <- (0 to (l.size - n)).toList;
                l1 = l.drop(i);
                sl <- comb(n-1, l1.tail))
            yield l1.head :: sl
}

这有点丑,我知道。我必须使用 toList 将范围(由“to”返回)转换为 List,以便“for”本身返回一个 List。我可以取消“l1”,但我认为这更清楚我在做什么。由于这里没有过滤器,因此修改它以删除重复项要容易得多:

def comb[T](n: Int, l: List[T]): List[List[T]] = {
  def comb1[T](n: Int, l: List[T]): List[List[T]] =
    n match {
      case 0 => List(List())
      case _ => for(i <- (0 to (l.size - n)).toList;
                    l1 = l.drop(i);
                    sl <- comb(n-1, l1.tail))
                yield l1.head :: sl
    }
  comb1(n, l).removeDuplicates
}
于 2009-07-02T12:32:49.320 回答
1

我在我的博客中写了一个类似的解决方案:http: //gabrielsw.blogspot.com/2009/05/my-take-on-99-problems-in-scala-23-to.html

首先,我想生成所有可能的组合并删除重复项,(或使用集合来处理重复项本身)但是由于问题是用列表指定的,并且所有可能的组合都太多了,所以我想出了对问题的递归解决方案:

要获得大小为 n 的组合,取集合中的一个元素并将其附加到其余元素的大小为 n-1 的集合的所有组合中,并合并其余元素的大小为 n 的组合。这就是代码的作用

 //P26
 def combinations[A](n:Int, xs:List[A]):List[List[A]]={
    def lift[A](xs:List[A]):List[List[A]]=xs.foldLeft(List[List[A]]())((ys,y)=>(List(y)::ys))

    (n,xs) match {
      case (1,ys)=> lift(ys)
      case (i,xs) if (i==xs.size) => xs::Nil
      case (i,ys)=> combinations(i-1,ys.tail).map(zs=>ys.head::zs):::combinations(i,ys.tail)
    }
 }

如何阅读:

我必须创建一个辅助函数,将列表“提升”为列表列表

逻辑在 match 语句中:

如果您想要列表元素的大小为 1 的所有组合,只需创建一个列表列表,其中每个子列表包含原始元素的一个元素(即“提升”功能)

如果组合是列表的总长度,则只返回一个列表,其中唯一的元素是元素列表(只有一种可能的组合!)

否则,取列表的头部和尾部,计算尾部大小为 n-1 的所有组合(递归调用)并将头部附加到每个结果列表(.map(ys.head::zs) )将结果与列表尾部大小 n 的所有组合连接起来(另一个递归调用)

是否有意义?

于 2009-07-02T15:19:37.720 回答
0

丹尼尔——我不确定亚历克斯所说的重复是什么意思,可能以下提供了更合适的答案:

def perm[T](n: Int, l: List[T]): List[List[T]] =
  n match {
    case 0 => List(List())
    case _ => for(el <- l.removeDuplicates;
                sl <- perm(n-1, l.slice(0, l.findIndexOf {_ == el}) ++ l.slice(1 + l.findIndexOf {_ == el}, l.size)))
            yield el :: sl
}

运行方式

perm(2, List(1,2,2,2,1)) 

这给出了:

List(List(2, 2), List(2, 1), List(1, 2), List(1, 1))

相对于:

List(
  List(1, 2), List(1, 2), List(1, 2), List(2, 1), 
  List(2, 1), List(2, 1), List(2, 1), List(2, 1), 
  List(2, 1), List(1, 2), List(1, 2), List(1, 2)
)

嵌套 perm 调用中的脏话是从列表中删除一个“el”,我想有一个更好的方法可以做到这一点,但我想不出一个。

于 2009-07-02T13:59:14.077 回答
0

该解决方案发布在 Rosetta Code 上:http ://rosettacode.org/wiki/Combinations_with_repetitions#Scala

def comb[A](as: List[A], k: Int): List[List[A]] = 
    (List.fill(k)(as)).flatten.combinations(k).toList
于 2012-09-21T06:21:08.407 回答
0

真的不清楚你在问什么。它可能是几个不同的事情之一。首先是列表中不同元素的简单组合。Scalacombinations()通过集合中的方法提供了这一点。如果元素是不同的,那么行为正是您对“组合”的经典定义所期望的。对于 p 元素的 n 元素组合,将有 p!/n!(pn)! 输出中的组合。

但是,如果列表中有重复的元素,Scala 将生成组合,并且该项目在组合中出现多次。但只是不同的可能组合,元素可能与输入中存在的次数一样多。它只生成可能组合的集合,所以重复的元素,而不是重复的组合。我不确定在它的基础上是否有一个实际的迭代器Set

现在,如果我理解正确,您的实际意思是来自一组给定的不同 p 元素的组合,其中一个元素可以在组合中重复出现 n 次。

好吧,回来一点,当输入中有重复元素时生成组合,并且您想在输出中看到重复的组合,解决方法就是使用 n 嵌套通过“蛮力”生成它循环。请注意,它实际上并没有什么粗鲁的东西,它只是组合的自然数,真的,对于小 n,它是 O(p^n),你对此无能为力。您只应小心正确选择这些值,如下所示:

val a = List(1,1,2,3,4)
def comb = for (i <- 0 until a.size - 1; j <- i+1 until a.size) yield (a(i), a(j))

导致

scala> comb
res55: scala.collection.immutable.IndexedSeq[(Int, Int)] = Vector((1,1), (1,2), (1,3), (1,4), (1,2), (1,3), (1,4), (2,3), (2,4), (3,4))

0 until a.size这通过首先创建as (i, j)...的中间组合,从 a 中的这些重复值生成组合。

现在要创建“重复组合”,您只需更改索引,如下所示:

val a = List('A','B','C')
def comb = for (i <- 0 until a.size; j <- i until a.size) yield (a(i), a(j))

会产生

List((A,A), (A,B), (A,C), (B,B), (B,C), (C,C))

但我不确定将其推广到更大组合的最佳方法是什么。

现在,当我找到这篇文章时,我将结束我正在寻找的内容:一个从包含重复元素的输入生成组合的函数,中间索引由combinations(). 很高兴这个方法产生一个列表而不是一个元组,所以这意味着我们实际上可以使用“地图的地图”来解决这个问题,我不确定其他人在这里提出过什么,但这很漂亮而且看过之后会让你对 FP 和 Scala 的爱更深一点!

def comb[N](p:Seq[N], n:Int) = (0 until p.size).combinations(n) map { _ map p }

结果是

scala> val a = List('A','A','B','C')
scala> comb(a, 2).toList
res60: List[scala.collection.immutable.IndexedSeq[Int]] = List(Vector(1, 1), Vector(1, 2), Vector(1, 3), Vector(1, 2), Vector(1, 3), Vector(2, 3))
于 2016-08-24T20:59:58.757 回答