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

私が歌川です

@utgwkk が書いている

Ruby で並べ替え問題じゃないときの樹形図(すべての事象)を書き出す

まずはじめに

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で出てくる階乗という計算、すなわち、

n! = n \times (n-1) \times (n-2) \times \cdots \times 3 \times 2 \times 1

というのはご存知だろうか。
この計算をするときには、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 = [['','×'],['','×'],['','×'],['','×']]

などのようにしてやれば、あら不思議、コイントス問題だって解けちゃう!!! すごい!!!! ヤバイ!!!!! 天変地異!!!!

ちなみに

単純な並べ替え問題を解くときは、また違う解き方があるようですね。

おさらい

  • 再帰関数は便利
  • 数字当てはめ問題、コイントス が解ける
  • 誰かコード改良して