【Ruby】【アルゴリズム】場合の数（「何通りか」問題）。メモ化がすごい！

　
さっきは全列挙したけれど
何通りか、を考えてみよう。

問題再掲

数が二つ与えられて、片方の数字を、
もう片方の数字以下の数字の組み合わせで表現する
何通りの方法が存在するか
（例）
１０　と　１　⇒[1,1,.....,1]　で1通り
４　と　３　⇒[3,1][2,2][2,1,1][1,1,1,1]　で４通り
４　と　２　⇒[2,2][2,1,1][1,1,1,1]　で3通り

考え方

何が再帰になるか

例えば「５を最大３の組み合わせで表現」するとき
「５を最大２の組み合わせで表現」＋「５を、必ず３を含めた最大３の組み合わせで表現」と分解することが出来る。

いろんな分解方法があると思うけれど、
さっきの全列挙のコードの中で、
state, m, n を出力してみて、何が繰り返しになっているか見つけてみる。

def separate(state, m, n)
  print state, " ", m, " ", n, " ", "\n"
  return if m <= 0
  if n==1
    state[1] = m
    @total_answer += 1
    return
  end
  0.step(m/n) do |i|
    next_state = state.dup
    next_state[n] = i if i != 0
    @total_answer += 1 if n*i==m
    separate(next_state, m-n*i, n-1)
  end
end
@total_answer = 0
tttotal_answer = separate({}, 10,10)
p @total_answer

　
■実行結果（一部）

{2=>4} 2 1
{3=>2, 2=>1} 2 1
{4=>1, 2=>2} 2 1
{4=>2} 2 1
{5=>1, 3=>1} 2 1
{6=>1, 2=>1} 2 1
{8=>1} 2 1

なるほど。
たしかにそれまでに「XXX」を作っていて、残りのmを最大nで表現する、
と考えれば再帰になる。

「今何を作っているか」の情報は、場合の数を求めるには不要な情報。
m,nだけを要素にメモ化すれば取ればよい。

まずはメモ化しないVerから。

コード

def separate(m, n)
  return 0 if m <= 0
  return 1 if n==1
  count = 0
  0.step(m/n) do |i|
    count += 1 if n*i==m
    count += separate(m-n*i, n-1)
  end
  count
end

　
次にこれをメモ化。

ハッシュ関数

def hash_key(m, n)
  (m.to_s + "_" + n.to_s).to_sym 
end

コード

def hash_key(m, n)
	(m.to_s + "_" + n.to_s).to_sym 
end
def separate(m, n)
  return @memo[hash_key(m, n)] if @memo[hash_key(m, n)]
  return 0 if m <= 0
  return 1 if n==1
  count = 0
  0.step(m/n) do |i|
    count += 1 if n*i==m
    count += separate(m-n*i, n-1)
  end
  @memo[hash_key(m, n)] = count
  count
end
@memo = {}
p separate(4, 3)
p separate(20, 10)
p separate(1000,10)

　
■実行結果

4
530
968356321790171

もっと大きな値を考えて、メモリが吹っ飛ぶ場合は、
何でもかんでもメモを取らず、メモを取る上限を決めておけばいい。
（小さい値ほどよく参照される）
ここで勉強したこと。

やった！