如何在不使用可变ArrayBuffer的情况下累积结果？
如何在不使用可变ArrayBuffer的情况下累积结果？
提问于 2013-03-18 11:25:31
此问题末尾的代码将0替换为1到9之间的可能数字一次，并且不重复。对于给定的数字序列List(0，0，1，5，0，0，8，0，0)，它将返回以下结果。总共有720个排列。
List(2, 3, 1, 5, 4, 6, 8, 7, 9)
List(2, 3, 1, 5, 4, 6, 8, 9, 7)
List(2, 3, 1, 5, 4, 7, 8, 6, 9)
List(2, 3, 1, 5, 4, 7, 8, 9, 6)
List(2, 3, 1, 5, 4, 9, 8, 6, 7)
List(2, 3, 1, 5, 4, 9, 8, 7, 6)
List(2, 3, 1, 5, 6, 4, 8, 7, 9)
...我的问题是，如何将代码转换为不使用ArrayBuffer(coll)作为临时存储，并从函数(search0)返回最终结果？
谢谢
/lim/
import collection.mutable.ArrayBuffer
object ScratchPad extends App {
def search(l : List[Int]) : ArrayBuffer[List[Int]] = {
def search0(la : List[Int], pos : Int, occur : List[Int], coll : ArrayBuffer[List[Int]]) : Unit = {
if (pos == l.length) {println(la); coll += la }
val bal = (1 to 9) diff occur
if (!bal.isEmpty) {
la(pos) match {
case 0 => bal map { x => search0(la.updated(pos, x), pos + 1, x :: occur, coll)}
case n => if (occur contains n) Nil else search0(la, pos + 1, n :: occur, coll)
}
}
}
val coll = ArrayBuffer[List[Int]]()
search0(l, 0, Nil, coll)
coll
}
println(search(List(0, 0, 1, 5, 0, 0, 8, 0, 0)).size)
}回答 2
Stack Overflow用户
回答已采纳
发布于 2013-03-18 13:42:55
下面是一个使用不可变集合的更短的解决方案：
scala> def search(xs: Seq[Int])(implicit ys: Seq[Int] = (1 to 9).diff(xs)): Seq[Seq[Int]] = ys match {
| case Seq() => Seq(xs)
| case _ => ys.flatten(y => search(xs.updated(xs.indexOf(0), y))(ys.diff(Seq(y))))
| }
search: (xs: Seq[Int])(implicit ys: Seq[Int])Seq[Seq[Int]]
scala> search(List(0, 0, 1, 5, 0, 0, 8, 0, 0)).size
res0: Int = 720
scala> search(List(0, 0, 1, 5, 0, 0, 8, 0, 0)) take 10 foreach println
List(2, 3, 1, 5, 4, 6, 8, 7, 9)
List(2, 3, 1, 5, 4, 6, 8, 9, 7)
List(2, 3, 1, 5, 4, 7, 8, 6, 9)
List(2, 3, 1, 5, 4, 7, 8, 9, 6)
List(2, 3, 1, 5, 4, 9, 8, 6, 7)
List(2, 3, 1, 5, 4, 9, 8, 7, 6)
List(2, 3, 1, 5, 6, 4, 8, 7, 9)
List(2, 3, 1, 5, 6, 4, 8, 9, 7)
List(2, 3, 1, 5, 6, 7, 8, 4, 9)
List(2, 3, 1, 5, 6, 7, 8, 9, 4)一个更短的解决方案：
scala> :paste
// Entering paste mode (ctrl-D to finish)
def search(xs: Seq[Int], ys: Seq[Int] = 1 to 9): Seq[Seq[Int]] = ys.diff(xs) match {
case Seq() => Seq(xs)
case zs => zs.flatten(z => search(xs.updated(xs.indexOf(0),z),zs))
}
// Exiting paste mode, now interpreting.
search: (xs: Seq[Int], ys: Seq[Int])Seq[Seq[Int]]
scala> search(List(0, 0, 1, 5, 0, 0, 8, 0, 0)).size
res1: Int = 720
scala> search(List(0, 0, 1, 5, 0, 0, 8, 0, 0)) take 10 foreach println
List(2, 3, 1, 5, 4, 6, 8, 7, 9)
List(2, 3, 1, 5, 4, 6, 8, 9, 7)
List(2, 3, 1, 5, 4, 7, 8, 6, 9)
List(2, 3, 1, 5, 4, 7, 8, 9, 6)
List(2, 3, 1, 5, 4, 9, 8, 6, 7)
List(2, 3, 1, 5, 4, 9, 8, 7, 6)
List(2, 3, 1, 5, 6, 4, 8, 7, 9)
List(2, 3, 1, 5, 6, 4, 8, 9, 7)
List(2, 3, 1, 5, 6, 7, 8, 4, 9)
List(2, 3, 1, 5, 6, 7, 8, 9, 4)Stack Overflow用户
发布于 2013-03-18 11:59:00
仅使用不可变的数据结构对代码进行天真的重构：
object ScratchPad extends App {
def search(l: List[Int]): List[List[Int]] = {
def search0(la: List[Int], pos: Int, occur: List[Int]): List[List[Int]] =
if (pos == l.length)
List(la)
else {
val bal = (1 to 9) diff occur
if (pos < l.length && !bal.isEmpty)
la(pos) match {
case 0 => bal.toList flatMap {x => search0(la.updated(pos, x), pos + 1, x :: occur)}
case n => if (occur contains n) List.empty[List[Int]] else search0(la, pos + 1, n :: occur)
}
else
List.empty[List[Int]]
}
search0(l, 0, Nil)
}
val result = search(List(0, 0, 1, 5, 0, 0, 8, 0, 0))
result foreach println
println(result.size)
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/15469303
复制相关文章
相似问题
腾讯云开发者
