Re:自然数の分割（別表現） - No Programming, No Life

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

下書き中で詰まってます

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