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) 作为我的临时存储，并从 function( 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)
}
4

2 回答 2

4

这是使用不可变集合的较短解决方案：

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)
于 2013-03-18T05:42:54.570 回答
0

仅使用不可变数据结构对代码进行天真的重构：

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)
}
于 2013-03-18T03:59:00.130 回答