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

せかいや

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

【Ruby】【アルゴリズム】連続して並ばない組み合わせの数

 

男子が18人、女子が22人いるクラスがある。これをランダムな順番で並ばせた時、女子・男子ともに5人以上が連続して並ばない確率を求めなさい

http://www.itmedia.co.jp/enterprise/articles/1005/15/news002_2.html

うーん。。18,22だとメモリが飛んでしまう。
 

def solve(total_zero, total_one, results, seed)
  return if seed.index("00000") ||  seed.index("11111") 
  return results << seed if total_zero==0 && total_one==0
  if total_zero > 0
    copy_for_zero = seed.dup
    copy_for_zero += "0" 
    solve(total_zero-1, total_one, results, copy_for_zero)
  end
  if total_one > 0
    copy_for_one = seed.dup
    copy_for_one += "1"
    solve(total_zero, total_one-1, results, copy_for_one)
  end
end
results = []
solve(18, 22, results, "")
p results.length