読者です 読者をやめる 読者になる 読者になる

せかいや

いまいるここを、おもしろく http://sekai-in-the-box.appspot.com/

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

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


 

問題再掲

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

考え方

何が再帰になるか

例えば「5を最大3の組み合わせで表現」するとき
「5を最大2の組み合わせで表現」+「5を、必ず3を含めた最大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

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


やった!