「ある金額になるコインの組み合わせ」をScalaで

続いてやってみた。お題はこちら。
お題:ある金額になるコインの組み合わせ - No Programming, No Life

あまり芸のない総当たりだけど、こんなんでいいのかな。

object CoinAssort {
    def search(coinList: List[Int], sum: Int, curAssort: List[Int] = Nil): List[List[Int]] = {
        val preCoin = curAssort.lastOption.getOrElse(0)
        coinList.filter(coin => coin >= preCoin && coin <= sum).flatMap(coin => {
            sum - coin match {
                case 0 => List(curAssort :+ coin)
                case n => search(coinList, n, curAssort :+ coin)
            }
        })
    }
}

/**
 * 以下テスト
 */
class CoinAssortTest {
    import org.junit.Assert._
    import org.junit.Test

    @Test
    def coinAssortTest = {
        val res = CoinAssort.search(List(1, 5, 10, 50, 100, 500), 10)
        assertTrue(res.exists(_ == List(1, 1, 1, 1, 1, 1, 1, 1, 1, 1)))
        assertTrue(res.exists(_ == List(1, 1, 1, 1, 1, 5)))
        assertTrue(res.exists(_ == List(5, 5)))
        assertTrue(res.exists(_ == List(10)))

        // 合計値の異なる組み合わせが混ざってないこと
        for (a <- res) assertEquals(10, a.sum)
        
        // 重複がないこと
        assertEquals(res.size, res.map(_.sorted).distinct.size)
    }
}

そういえば、Eclipse indigo + Scalaプラグインの最新版だと、JUnitライブラリのimportを最上位スコープに出さなくとも、Run Asからテスト実行できるようになってますね。こりゃいいや。

(8/17追記) スタック溢れ対策(失敗)版

上記コードでは、樹形探索の各ノードで単純に再帰呼出しをしているので、金額が1000円くらいになると再帰が深くなって容易にスタックオーバーフローを起こしてしまいます(32bit環境の場合)。

ということで対策版。修正ポイントは以下になります。

  • コインの組合せ情報のコンテナAssortを作成し、このコンテナの型によって探索状態を持たせる
  • 末尾再帰となるように、個々のノードで再帰するのではなく、状態判断と組合せパターンの分岐のみ行って、組合せのリストをまるごと継続渡しで再帰関数に渡す。

…が、ヒープの消費量が異常に大きくなってしまい、スタック溢れの代わりにOutOfMemoryErrorになります。たぶん組合せリストそのものが肥大化するのと、再帰の段数が増えるごとに新リストを生成して、参照が切れないまま維持されるのが原因でしょう。さてどうしたもんか。

(8/20)
このコードを添削して頂き、Listに :+ を繰り返すのは非常に効率が悪いこと、Streamで巨大なリストの評価を遅延させることができることをご指摘頂きました。ありがとうございます。
勝手に添削:「「ある金額になるコインの組み合わせ」をScalaで」 - kmizuの日記

object CoinAssort2 {

    sealed trait Assort                                             // Assort: コイン組み合わせパターンのコンテナ
    case class Over extends Assort                                  // 金額オーバー(破棄)
    case class Fixed(l: List[Int]) extends Assort                   // 確定済み
    case class Cont(l: List[Int], shorted: Int) extends Assort      // 探索途中
    object Assort {
        def apply(sum: Int, coin: Int, l: List[Int] = Nil) = sum - coin match {
            case 0 => Fixed(l :+ coin)
            case n if (n > 0) => Cont(l :+ coin, n)
            case _ => Over()
        }
    }

    def search(coinList: List[Int], sum: Int): List[List[Int]] = {

        val coins = coinList.filter(_ <= sum)

        def _search(curAssorts: List[Assort]): List[Assort] = {
            val res = curAssorts.flatMap(_ match {
                case Cont(l, shorted) => {
                    val preCoin = l.lastOption.getOrElse(0)
                    coins.filter(c => c >= preCoin && c <= shorted)
                        .flatMap(Assort(shorted, _, l) match {
                            case Over() => Nil
                            case x => List(x)
                        })
                }
                case assort => List(assort)
            })
            if (res.forall(_.isInstanceOf[Fixed])) res else _search(res) // 再帰
        }

        val initAssorts = coins.map(Assort(sum, _))
        _search(initAssorts).flatMap(_ match {
            case Fixed(l) => List(l)
            case _ => Nil
        })
    }
}

(8/18追記) スタック溢れ対策(Actor使用)版

無理に末尾再帰にすると、継続の肥大化が避けられないので諦めました。

再帰の際に関数呼び出しを使うからスタックを消費するのであって、それさえなければ樹形再帰でも問題ないはず。ということで、最低限の継続情報をキューに放り込み、放り込まれた順番に処理して、分岐したらその分をまたキューに放り込み…という形を考えてみました。ついでに、Actorを使って並行処理させてみます。

他にも、無節操にListを使っていたのを、一部Arrayに切り替えたりしています。

object CoinAssort3 {

    type Assort = Array[Int]
    object Assort { def apply() = Array[Int]() }
    case class Cont(assort: Assort, shorted: Int)  // 組合せ探索の継続情報コンテナ

    def search(coinList: List[Int], sum: Int): List[Assort] = {
        
         // 確定済情報を格納する可変バッファ
        import scala.collection.mutable.{ArrayBuffer, SynchronizedBuffer}
        val fixedBuf = new ArrayBuffer[Assort] with SynchronizedBuffer[Assort]
        
        // 再帰処理を行うActor
        import scala.actors.Actor
        val _search = new Actor() {     
            def act() = loop {
                react {
                    case c: Cont => checkNode(c)
                    case None => exit
                    case _ =>
                }
            }

            private def checkNode(cont: Cont) = {
                val (assort, shorted) = (cont.assort, cont.shorted)
                val preCoin = assort.lastOption.getOrElse(0)
                coinList.filter(x => x >= preCoin && x <= shorted)
                    .foreach(coin => shorted - coin match {
                        case 0            => fixedBuf += (assort :+ coin)
                        case n if (n > 0) => this ! Cont(assort :+ coin, n) // 再帰
                        case _            => 
                    })
            }
        }
        
        _search.start
        _search ! Cont(Assort(), sum)
        while(_search.getState == Actor.State.Runnable){ Thread.`yield` }
        _search ! None
       
        fixedBuf.toList
    }
}