在Scala中从List[List[Int]]生成所有可能的组合

5vf7fwbs 于 2023-02-19 发布在 Scala

关注(0)|答案(5)|浏览(181)

给定以下列表：

List(List(1,2,3), List(4,5))

我想生成所有可能的组合。使用yield，可以如下所示：

scala> for (x <- l.head; y <- l.last) yield (x,y)
res17: List[(Int, Int)] = List((1,4), (1,5), (2,4), (2,5), (3,4), (3,5))

但我遇到的问题是List [List [Int]]不是固定的;它的大小可以增长和收缩，所以我永远不知道我需要多少个for循环。我希望能够将该列表传递给一个函数，该函数将动态生成组合，而不管我拥有的列表数量如何，因此：

def generator (x : List[List[Int]) : List[List[Int]]

是否有一个内置的库函数可以做到这一点。如果没有，我怎么去做这一点。任何指针和提示将是伟大的。
更新：
@DNA给出的答案会用下面的嵌套List结构（不太大）来破坏堆：

List(

    List(0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80, 85, 90, 95, 100, 105, 110, 115, 120, 125, 130, 135, 140, 145, 150, 155, 160, 165, 170, 175, 180, 185, 190, 195, 200, 205, 210, 215, 220, 225, 230, 235, 240, 245, 250, 255, 260, 265, 270, 275, 280, 285, 290, 295, 300), 
    List(0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 130, 140, 150, 160, 170, 180, 190, 200, 210, 220, 230, 240, 250, 260, 270, 280, 290, 300), 
    List(0, 20, 40, 60, 80, 100, 120, 140, 160, 180, 200, 220, 240, 260, 280, 300), 
    List(0, 50, 100, 150, 200, 250, 300), 
    List(0, 100, 200, 300), 
    List(0, 200), 
    List(0)

    )

调用generator2函数，如下所示：

generator2(
      List(
        List(0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80, 85, 90, 95, 100, 105, 110, 115, 120, 125, 130, 135, 140, 145, 150, 155, 160, 165, 170, 175, 180, 185, 190, 195, 200, 205, 210, 215, 220, 225, 230, 235, 240, 245, 250, 255, 260, 265, 270, 275, 280, 285, 290, 295, 300),
        List(0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 130, 140, 150, 160, 170, 180, 190, 200, 210, 220, 230, 240, 250, 260, 270, 280, 290, 300),
        List(0, 20, 40, 60, 80, 100, 120, 140, 160, 180, 200, 220, 240, 260, 280, 300),
        List(0, 50, 100, 150, 200, 250, 300),
        List(0, 100, 200, 300),
        List(0, 200),
        List(0)
      )
    )

有没有一种方法可以生成笛卡尔积而不破坏堆？

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
    at scala.LowPriorityImplicits.wrapRefArray(LowPriorityImplicits.scala:73)
    at recfun.Main$.recfun$Main$$generator$1(Main.scala:82)
    at recfun.Main$$anonfun$recfun$Main$$generator$1$1.apply(Main.scala:83)
    at recfun.Main$$anonfun$recfun$Main$$generator$1$1.apply(Main.scala:83)
    at scala.collection.TraversableLike$$anonfun$flatMap$1.apply(TraversableLike.scala:251)
    at scala.collection.TraversableLike$$anonfun$flatMap$1.apply(TraversableLike.scala:251)
    at scala.collection.immutable.List.foreach(List.scala:318)
    at scala.collection.TraversableLike$class.flatMap(TraversableLike.scala:251)
    at scala.collection.AbstractTraversable.flatMap(Traversable.scala:105)
    at recfun.Main$.recfun$Main$$generator$1(Main.scala:83)
    at recfun.Main$$anonfun$recfun$Main$$generator$1$1.apply(Main.scala:83)
    at recfun.Main$$anonfun$recfun$Main$$generator$1$1.apply(Main.scala:83)
    at scala.collection.TraversableLike$$anonfun$flatMap$1.apply(TraversableLike.scala:251)
    at scala.collection.TraversableLike$$anonfun$flatMap$1.apply(TraversableLike.scala:251)
    at scala.collection.immutable.List.foreach(List.scala:318)
    at scala.collection.TraversableLike$class.flatMap(TraversableLike.scala:251)
    at scala.collection.AbstractTraversable.flatMap(Traversable.scala:105)
    at recfun.Main$.recfun$Main$$generator$1(Main.scala:83)
    at recfun.Main$$anonfun$recfun$Main$$generator$1$1.apply(Main.scala:83)
    at recfun.Main$$anonfun$recfun$Main$$generator$1$1.apply(Main.scala:83)
    at scala.collection.TraversableLike$$anonfun$flatMap$1.apply(TraversableLike.scala:251)
    at scala.collection.TraversableLike$$anonfun$flatMap$1.apply(TraversableLike.scala:251)
    at scala.collection.immutable.List.foreach(List.scala:318)
    at scala.collection.TraversableLike$class.flatMap(TraversableLike.scala:251)
    at scala.collection.AbstractTraversable.flatMap(Traversable.scala:105)
    at recfun.Main$.recfun$Main$$generator$1(Main.scala:83)
    at recfun.Main$$anonfun$recfun$Main$$generator$1$1.apply(Main.scala:83)
    at recfun.Main$$anonfun$recfun$Main$$generator$1$1.apply(Main.scala:83)
    at scala.collection.TraversableLike$$anonfun$flatMap$1.apply(TraversableLike.scala:251)
    at scala.collection.TraversableLike$$anonfun$flatMap$1.apply(TraversableLike.scala:251)
    at scala.collection.immutable.List.foreach(List.scala:318)
    at scala.collection.TraversableLike$class.flatMap(TraversableLike.scala:251)

scala

来源：https://stackoverflow.com/questions/23425930/generating-all-possible-combinations-from-a-listlistint-in-scala

5条答案

按热度按时间

eagi6jfj1#

下面是一个递归解决方案：

def generator(x: List[List[Int]]): List[List[Int]] = x match {
    case Nil    => List(Nil)
    case h :: _ => h.flatMap(i => generator(x.tail).map(i :: _))
  }

其产生：

val a = List(List(1, 2, 3), List(4, 5))       
val b = List(List(1, 2, 3), List(4, 5), List(6, 7))

generator(a)    //> List(List(1, 4), List(1, 5), List(2, 4), 
                //| List(2, 5), List(3, 4), List(3, 5))
generator(b)    //> List(List(1, 4, 6), List(1, 4, 7), List(1, 5, 6), 
                //| List(1, 5, 7), List(2, 4, 6), List(2, 4, 7),
                //| List(2, 5, 6), List(2, 5, 7), Listt(3, 4, 6), 
                //| List(3, 4, 7), List(3, 5, 6), List(3, 5, 7))

**更新：**第二个case也可以写成for理解，这样可能更清楚一些：

def generator2(x: List[List[Int]]): List[List[Int]] = x match {
  case Nil    => List(Nil)
  case h :: t => for (j <- generator2(t); i <- h) yield i :: j
}

**更新2：**对于较大的数据集，如果内存不足，可以改用流（如果增量处理结果有意义）。例如：

def generator(x: Stream[Stream[Int]]): Stream[Stream[Int]] = 
  if (x.isEmpty) Stream(Stream.empty) 
  else x.head.flatMap(i => generator(x.tail).map(i #:: _))

// NB pass in the data as Stream of Streams, not List of Lists
generator(input).take(3).foreach(x => println(x.toList))

>List(0, 0, 0, 0, 0, 0, 0)
>List(0, 0, 0, 0, 0, 200, 0)
>List(0, 0, 0, 0, 100, 0, 0)

赞(0）回复(0）举报 2023-02-19

zf9nrax12#

感觉你的问题可以用递归来描述：
如果有n个int列表：大小为m的列表1和列表2，...列表n

生成列表2到n的X个组合（因此n-1个列表）
对于每个组合，为list 1的每个值生成m个新的。
基本情况是一个int列表的列表，你只需要把所有元素拆分成单例列表.

所以对于List（List（1，2），List（3），List（4，5）），递归调用的结果是List（List（3，4），List（3，5）），并且为每一个添加两个组合：列表（1、3、4）、列表（2、3、4）、列表（1、3、5）、列表（2、3、5）。

赞(0）回复(0）举报 2023-02-19

gdrx4gfi3#

以西结正是我要找的。这只是一个小的调整，使它通用。

def generateCombinations[T](x: List[List[T]]): List[List[T]] = {
    x match {
      case Nil => List(Nil)
      case h :: _ => h.flatMap(i => generateCombinations(x.tail).map(i :: _))
    }
  }

赞(0）回复(0）举报 2023-02-19

3htmauhk4#

这是另一个基于以西结的解决方案，更冗长，但它是尾部递归（栈安全）。

def generateCombinations[A](in: List[List[A]]): List[List[A]] =
    generate(in, List.empty)

  @tailrec
  private def generate[A](in: List[List[A]], acc: List[List[A]]): List[List[A]] = in match {
    case Nil          => acc
    case head :: tail => generate(tail, generateAcc(acc, head))
  }

  private def generateAcc[A](oldAcc: List[List[A]], as: List[A]): List[List[A]] = {
    oldAcc match {
      case Nil => as.map(List(_))
      case nonEmptyAcc =>
        for {
          a  <- as
          xs <- nonEmptyAcc
        } yield a :: xs
    }
  }

赞(0）回复(0）举报 2023-02-19

9jyewag05#

我知道这是旧的，但似乎没有其他答案提供了非递归解决方案与折叠。

def generator[A](xs: List[List[A]]): List[List[A]] = xs.foldRight(List(List.empty[A])) { (next, combinations) =>
  for (a <- next; as <- combinations) yield a +: as
}

赞(0）回复(0）举报 2023-02-19

我来回答

在Scala中从List[List[Int]]生成所有可能的组合

5条答案

相关问题

热门标签

最新问答