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

5vf7fwbs  于 2023-02-19  发布在  Scala
关注(0)|答案(5)|浏览(180)

给定以下列表:

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

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

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

gdrx4gfi

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 :: _))
    }
  }
3htmauhk

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
    }
  }
9jyewag0

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
}

相关问题