0

この質問の最後にあるコードは、ゼロを 1 から 9 までの範囲の可能な数字で 1 回だけ、繰り返しのないものに置き換えます。指定された一連の数値 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)
...

coll私の質問は、一時ストレージとしてArrayBuffer( ) を使用しないようにコードを変換し、最終結果がsearch0代わりに function( ) から返されるようにするにはどうすればよいですか?

ありがとう

/リム/

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 に答える