如何在不使用可變ArrayBuffer的情況下累積結果？

Question

該問題末尾的代碼將可能的數字從1到9替換爲0，並且不重複。對於給定的數字序列，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) 
} 

Answer 1

這裏是一個較短的解決方案使用不可變集合：

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) 

Answer 2

只用一成不變的數據結構代碼的樸素重構：

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