No Programming, No Life

新しいNPNLです。http://d.hatena.ne.jp/fumokmm/ から引っ越してきました。

Re:自然数の分割(別表現)

お題: Server error
投稿: Server error


下書き中で詰まってます。下記コードだと、出力される組み合わせが足りない。

下書き中で詰まってます

def num = args[0].toInteger()
println "young ${num}"

def startTime = System.currentTimeMillis()
young(num)
def finishTime = System.currentTimeMillis()

println "elapsed time: ${(finishTime - startTime) / 1000}sec."

// ヤング図形をすべて出力
def young(num) {
   def list = [num]
   out(list)
   def count = 1
   while (!list.every{ it == 1 }) {
      transform2NextPartition(list)
      out(list)
      count++
   }
   println "${count} combinations were found."
}

// 次の分割数へ変換 例) [3, 2] -> [3, 1, 1]
def transform2NextPartition(list){
   def from = {
      // 長さが短いもの
      int idx = list.findLastIndexOf{ it > 1 }
      if (idx != -1) return idx
      // 辞書順で大きいもの
      return list.findLastIndexOf{ it == list.first() }
   }()
   if (from != -1) {
      def to = list.findIndexOf{ it < list[from] - 1 }
      if (to != -1) list[to]++ else list << 1
      list[from]--
   }
}

// 出力
def out(list) {
   list.each{ println ('□'*it) }; println ''
}

詰まってる内容


def from = {
// 長さが短いもの
int idx = list.findLastIndexOf{ it > 1 }
if (idx != -1) return idx
// 辞書順で大きいもの
return list.findLastIndexOf{ it == list.first() }
}()

の部分で、「長さが短いもの」と「辞書順で大きいもの」で、「長さが短いもの」を優先して選んでいるつもりなんですが、これ、list.findLastIndexOf{ it > 1 }list.findLastIndexOf{ it == list.first() }が両方ともidx != -1でない場合が、存在するんで*1、ここから先はそれぞれのルートを再起で繰り返す必要があるんかなぁ、やっぱり。

追記 (2009-02-13)

色々練って、結局再起でやることにしました。
こんな感じ。

def num = args[0].toInteger()
println "young ${num}"
println ''
def startTime = System.currentTimeMillis() // 開始時刻
def youngList = partitions(num) // 分割リストを取得
youngList.each{ out(it) } // 出力
println "${youngList.size()} combinations were found."
def finishTime = System.currentTimeMillis() // 終了時間
println "elapsed time: ${(finishTime - startTime) / 1000} (sec)"

// 分割リストを取得
def partitions(num) { div(num, num) }

// リストを分割
def div(num, limit) {
    if (num == 1) return [[1]]
    def pairCollect = { n, yield ->
        [n..1, 0..<n].transpose().findAll{ it[0] <= limit }
        .collect{ yield(it[0], it[1]) }
    }
    def list = pairCollect(num){ left, right ->
        if (right == 0)
            return [[left]]
        if (left <= right)
            return div(right, left).collect{ [left, it].flatten() }
        else
            return div(right, right).collect{ [left, it].flatten() }
    }
    def result = []
    list.each{ result.addAll( it ) }
    return result
}

// 出力
def out(list) {
    println list
    list.each{ println('□' * it) }
    println ''
}

考察

young 50ともなると204226種類の組み合わせが見つかり、激遅です。うちのマシンだと、551.11secでした。groovycにコンパイルしてやってみたら321.093secまでスピードアップしました。

完全なリストを一度作ってから出力するという戦略が悪いようですね。
効率よくやるには、リストを作りつつ出力しちゃうっていうのがあるだろうな。

また、時間があったら改良しよう。

*1:[4, 2] の次は [3, 3] or [4, 1, 1]