モンモールの問題

montmort.rb

#!/usr/bin/env ruby

# モンモールの問題
# http://blog.livedoor.jp/maraigue/archives/884785.html

MAX = 20

# 順列を計算する
class Integer
  def P(other) # a.P(b) と書くことで aPb を計算できるようにする
    ((self - other + 1)..self).inject(1){ |a, b| a*b }
  end
end

result = [1, 0] # a_0 = 1, a_1 = 0 に相当
all_case = 1

2.upto MAX do |n|
  # すべての傘の持ち帰り方
  all_case *= n
  
  # a_nを、誰も自分の傘を持ち帰らないような持ち帰り方の総数とすると
  # a_n = Σ_{t=2}^{n} a_{n-t}・{n-1}P{t-1}
  result[n] = 0
  for t in 2..n
    result[n] += result[n-t] * (n-1).P(t-1)
  end
  
  printf "%3d guests: %12.10f (#{all_case - result[n]}/#{all_case})\n",
    n, 1.0 - result[n].to_f/all_case
end