【アルゴリズム】【Ruby】深さ優先検索、ハッシュを使ったメモリ節約、参照渡し・値渡し（インスタンスを利用したカウンタ）

初めて「探索」の考え方に触れたときの問題を改めて考えてみる。
一ヶ月前かー。

問題再掲

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

以前の考え方

合計がmになる組み合わせをとりあえず全部列挙する。
出した組み合わせの中から、nより大きい数字を使っている組み合わせをはじく

今回のポイント

「とりあえず全部列挙」ではなく、
10が何個入るか、、9が何個入るか、、8が何個入るか、、を深さ優先で繰り返していく。
ハッシュを使ってメモリを節約する。

コード

むちゃくちゃ！コードが！短くなってる！

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

■実行結果

[{1=>10}, {2=>1, 1=>8}, {2=>2, 1=>6}, {2=>3, 1=>4}, {2=>4, 1=>2}, {2=>5}, {3=>1, 1=>7}, {3=>1, 2=>1, 1=>5}, {3=>1, 2=>2, 1=>3}, {3=>1, 2=>3, 1=>1}, {3=>2, 1=>4}, {3=>2, 2=>1, 1=>2}, {3=>2, 2=>2}, {3=>3, 1=>1}, {4=>1, 1=>6}, {4=>1, 2=>1, 1=>4}, {4=>1, 2=>2, 1=>2}, {4=>1, 2=>3}, {4=>1, 3=>1, 1=>3}, {4=>1, 3=>1, 2=>1, 1=>1}, {4=>1, 3=>2}, {4=>2, 1=>2}, {4=>2, 2=>1}, {5=>1, 1=>5}, {5=>1, 2=>1, 1=>3}, {5=>1, 2=>2, 1=>1}, {5=>1, 3=>1, 1=>2}, {5=>1, 3=>1, 2=>1}, {5=>1, 4=>1, 1=>1}, {5=>2}, {6=>1, 1=>4}, {6=>1, 2=>1, 1=>2}, {6=>1, 2=>2}, {6=>1, 3=>1, 1=>1}, {6=>1, 4=>1}, {7=>1, 1=>3}, {7=>1, 2=>1, 1=>1}, {7=>1, 3=>1}, {8=>1, 1=>2}, {8=>1, 2=>1}, {9=>1, 1=>1}, {10=>1}]

「何通りあるか」だけ知りたい場合

answers をtotal_answer にするだけではうまくいかないよ。

total_answer = 0
separate(total_answer, {}, 10000,10)
p total_answer

当然 0 が出力されてしまう。

数値は参照渡しではなく値渡しだから、
渡したメソッド内での変更が元の値に反映されない
（元のオブジェクトに影響を与えない）

def hoge(st1)
p st1.object_id  #<=1
  st1 += 1
p st1.object_id  #<=3
end
st = 0
p st.object_id  #<=1
hoge(st)
p st            #<=0
p st.object_id  #<=1

こういう感じ。
st1にstの値を渡した時点 (st1=st）で値がコピーされている
（実際は参照を渡していて同じ参照先を見続けているが、数値はimmutableなので、
値が変更された時点で参照先が変更されるので値渡しと表現して問題ない。
内部的にはRuby処理系は一般にFixnumを参照ではなく即値で扱う）

説明が難しい。。

Ruby2.1では文字列のフローズンリテラル記法が出るみたいだけれど、
慣れてない人が理解するのはちょっと難しそう。
Stringの +=メソッドではobject_idが変わる、<<メソッドでは変らない、とか？

興味ある人がいればまとめるけどまあいないか。

話がそれた！

　
インスタンス変数を使うと解決できる。

@total_answer = 0
separate(@total_answer, {}, 10000,10)
p @total_answer

　
オブジェクトクラスへのインスタンス変数は行儀が悪いと感じるなら
明示的にインスタンスを作る方法もある。

class Answer
  def initialize(count)
    @count = count
  end
  attr_accessor :count
end
answer = Answer.new(0)
separate(answer, {}, 10,10)
p answer.count

　
おしまい。