まずはじめに
「Ruby 樹形図」でググっても、アルファベットを並べ替えるというのしか出てこないワケです。
ちゃうねん！ ぼくが求めているのは、そっちの樹形図じゃない。
たとえば、コインを4つ投げたときの表裏の出方の全ての場合を書き出したい、というのが近い。
これがねえ、簡単そうでなかなか難しいわけですよ。
たとえば、
(1,2,3,4)(1,2,3)(1,2) ()の数字は、そこに入りうる数字である このとき、起こりうる全ての事象(数字の組み合わせ)を書き出せ。
この問題を考えるときに、1番目の括弧には1,2,3,4、2番目には1,2,3、3番目には1,2、と考えるために、
lst = [[1,2,3,4],[1,2,3],[1,2]]
という2次配列 lst を定義する。
プログラムを実行したら、
111 112 121 122 131 132 211 212 221 222 231 232 311 312 321 322 331 332 411 412 421 422 431 432
と表示されればよいのである！
できれば、場合分けの数に関係なく同じコードで解けるようにしたい。
問題文が固定されているなら、
@lst = [ [1,2,3,4], [1,2,3], [1,2] ] lst[0].length.times do |i| lst[1].length.times do |j| lst[2].length.times do |k| print lst[0][i],lst[1][j],lst[2][k] puts end end end
まあこれでもよいだろう。
それで、柔軟に対応できるコードを書こうとしたが、いかんせんうまくいかない。ううむ。
……再帰関数？ これだ！！
再帰関数？
たとえば、数学Aで出てくる階乗という計算、すなわち、
というのはご存知だろうか。
この計算をするときには、for文を使わなければならないのだろうなあ、と思われがち(間違いではない)だが、実は、次のようにも書ける。
def fac(n) return n == 1 ? n : n * fac(n-1) end puts fac(5)
実行結果
120
このコードでは、関数 fac(n) の中で、n == 1 でないなら n * fac(n-1) と、自分自身を呼び出しているのである。
それを n == 1 となるまで繰り返す。これが再帰関数の典型例である。
ただ、条件分岐などもせず(いつ切り上げるかを決めず)に再帰関数を呼び出していたら、ハングアップしてしまう。ご注意。
気を取り直して
できあがったコードがこれだ。
@lst = [ [1,2,3,4], [1,2,3], [1,2] ] @a = Array.new @a.fill(0,0..@lst.size-1) def jukeizu(an) if an == -1 then @lst.size.times do |i| print @lst[i][@a[i]] end puts else @lst[an].size.times do |b| @a[an] = b jukeizu(an-1) end @a[an] = 0 end end jukeizu(@lst.length-1)
再帰関数をうまく使った、風味の良いテイストになっているねえ。
実行結果
111 211 311 411 121 221 321 421 131 231 331 431 112 212 312 412 122 222 322 422 132 232 332 432
まあよいだろう。これで全ての場合が求められた。樹形図の完成！ えらいこっちゃ。
@lst = [['○','×'],['○','×'],['○','×'],['○','×']]
などのようにしてやれば、あら不思議、コイントス問題だって解けちゃう！！！ すごい！！！！ ヤバイ！！！！！ 天変地異！！！！
ちなみに
単純な並べ替え問題を解くときは、また違う解き方があるようですね。
