Как я могу накапливать результаты без использования изменяемого массива ArrayBuffer?

Question

Код в конце этого вопроса заменяет нули возможными номерами от 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) вместо этого?

Благодаря

/Нт/

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