Scala整数集合的可能组合

Question

我已经编写了以下代码来返回整数数组的所有可能组合

def  findAllCombinations ( remain:Array[Int], partial:Array[Int],cum :List[Array[Int]]) : List[Array[Int]]=  {
  for ( i <- 0 until remain.size) {
    val m = partial ++ Array(remain(i))
    val n = m::cum
    findAllCombinations(remain.slice(i+1 ,remain.size),m,n)
  }
  cum
}

当我使用下面的参数调用这个函数时，我得到的列表是空的。

findAllCombinations(Array(1,2,3),Array(),List(Array()))

有人能帮我改进代码吗？

Answer 1

在您的代码中，for导致调用findAllCombinations，但随后它返回调用基调用的cum，即List(Array())。

• 0 until remain.size的计算结果为scala.collection.immutable.Range
• for ( i <- 0 until remain.size) { ... }，https://www.scala-lang.org/files/archive/spec/2.11/06-expressions.html#for-comprehensions-and-for-loops

的计算结果为(0 until remain.size).foreach({ ... })，该值的计算结果为Unit (无论在块中执行了什么操作)

• 请参见documentation: See

for循环中发生了什么并不重要，因为cum无论如何都是从基调用返回的

如果你不想要排列，但是“组合”指的是“子集”(即获得原始集合的幂集)：

def findAllCombinations(remain:Seq[Int]) : List[Seq[Int]]=  {
  remain match {
    case head :: tail =>
      val tailCombinations = findAllCombinations(tail)
      tailCombinations.flatMap((combo: Seq[Int]) => Seq(head +: combo, combo))
    case _ => List(Seq())
  }
}
val x = findAllCombinations(Seq(1,2,3))
println(x)
println(x.length)

输出：

List(List(1, 2, 3), List(2, 3), List(1, 3), List(3), List(1, 2), List(2), List(1), List())
8