自然数の分割 in Ruby DouKaku?

自然数nとm(n>=m>0)が与えられたとき，nをm個の非負の整数の和で表すやり方を全て出力してください．
その際，和の組(x_1, ..., x_m)は大きい順に出力してください．
ここでm = 3の時の「(a, b, c)が(A, B, C)より大きい」とは
(a > A)
(a == A) かつ (b > B)
(a == A) かつ (b == B) かつ (c > C)
のいずれかが成り立つとき(つまりは辞書的順序)とします．

例:n = 5, m = 3が与えられたときは
5, 0, 0,
4, 1, 0,
4, 0, 1,
3, 2, 0,
3, 1, 1,
...
0, 1, 4,
0, 0, 5,
を出力する．

まずは，非常に安直な実装で．

はじめに，0以上n以下の数値からなる要素m個のArrayについて，考えうる全ての組み合わせを求めます．例えば，n = 3, m =2 の場合は:

> [[0, 0], [0, 1], [0, 2], [0, 3],
>  [1, 0], [1, 1], [1, 2], [1, 3],
>  [2, 0], [2, 1], [2, 2], [2, 3],
>  [3, 0], [3, 1], [3, 2], [3, 3]]

次に，このArrayを走査し，総和がnと一致するものだけを抽出し，ソートして解とします:

> [[3, 0], [2, 1], [1, 2], [0, 3]]

添削，ツッコミ，diff希望します:-)

require 'pp'

class NumericArray < Array
  def initialize(maxvalue, level)
    self[0, 0] = [0] * level
    @maxvalue = maxvalue
  end

  def succ
    self.dup.succ!
  end

  def succ!
    result = []
    carry = reverse.inject(1) do |carry, cur|
      if cur + carry < @maxvalue then
        result << cur + carry
        carry = 0
      else
        result << 0
        carry = 1
      end
    end
    return nil if carry == 1
    replace(result.reverse)
  end

  def sum
    inject(0) {|sum, i| i + sum}
  end
end


begin
  raise '2 arguments required.' if ARGV.size != 2
  sum, maxlevel = ARGV.map {|n| n.to_i }

  if sum <= 0 or maxlevel <= 0 then
    raise 'Arguments out of range.'
  end
rescue
  puts <<-_EOD_
#{File.basename($0)}: ERROR: #{$!}
usage: #{File.basename($0)} n m
  _EOD_
  exit(1)
end

xs = NumericArray.new(sum + 1, maxlevel)
result = []
begin
  result << xs.dup
end while xs.succ!.nil? == false

pp result.select {|list| list.sum == sum}.sort.reverse

rubyが無かったので書いてみたら、もうあった orz

def part_number(n, m)
  return [[n]] if m == 1
  table = Array.new(n+1)
  0.upto(n) do |i|
    list = []
    0.upto(i) do |j|
      list << [i-j, j]
    end
    table[i] = list
  end
  3.upto(m) do |p|
    new_table = Array.new(n+1)
    0.upto(n) do |i|
      new_table[i] = []
      0.upto(i) do |j|
        table[j].inject(new_table[i]) {|res, l| res << ([i-j] + l)}
      end
    end
    table = new_table
  end
  table[n]
end

m = (ARGV.shift || 5).to_i
n = (ARGV.shift || 3).to_i
part_number(m, n).each do |a|
  puts a.join(',')
end

行数を減らしてみた。

def part_number(n, m)
  table = Array.new(n+1) {|i| [[i]] }
  2.upto(m) do |p|
    table = Array.new(n+1) do |i|
      (0..i).inject([]) do |list, j|
        table[j].inject(list) {|res, l| res << ([i-j] + l)}
      end
    end
  end
  table[n]
end

m = (ARGV.shift || 5).to_i
n = (ARGV.shift || 3).to_i
part_number(m, n).each do |a|
  puts a.join(',')
end

例えば(5,3)の場合、基数変換で[5,0,0]から[0,0,5]までの配列を生成後、合計が5のものだけ出力しています。

def divNat(n,m)
  ((n + 1)**(m - 1) * n).downto(0) {|i|
    w = sprintf("%0#{m}d",i.to_s(n + 1)).split(//).map {|j|j.to_i}
    p w if w.inject(0){|r,j|r += j} == n
  }
end

divNat(5,3)

分解後の数字が2桁の場合の処理を簡潔に書く方法を思いつかなかったのと、スピードアップのために方針変更。 1桁目はnから0、2桁目は(n-1桁目)から0、...としました。

def divNat(n, m, acc = [])
  if m == 1
    p acc << n
    return
  end
  n.downto(0) {|i|
    w = acc[0..-1]
    divNat(n-i,m-1, w << i)
  }
end

divNat(5,3)

DouKaku?

自然数の分割

Posted feedbacks - Ruby

Index

Feed

Other

Link

Pathtraq