slotMachine.rb

# 数学的な処理をまとめた名前空間
class MathEx

	# 1からnの階乗を行う
	def self.fact(n)
		(1..n).inject(:*)
	end

	# nPrを計算する
	def self.p(n, r)
		return fact(n) if n == r
		MathEx.fact(n) / MathEx.fact(n - r)
	end

end

# スロット・マシン問題を解くにあたって利用するメソッドをまとめた名前空間
class Slot

	# パターンの一覧を配列に格納する
	def self.patterns(l)
		# 未確定なパターンと確定したパターン列を格納する配列
		patterns = (1...l).map{|i| [i]}
		defines = [[l]]

		# パターンに対して、最後に格納された数字と同じかそれより大きい数字を
		# ひとつ挿入して新しいパターン列を作る
		# 新たに作られたパターンに対し、その合計がlと等しい場合は確定済みへ
		# 小さい場合は未確定とする。大きくなった場合は破棄
		until patterns.empty? do
			temps = []
			patterns.each do |pattern|
				(pattern.last...l).each do |tail|
					temp = pattern.dup.push(tail)
					sum = temp.inject(:+)

					defines << temp if sum == l
					temps   << temp if sum < l
				end
			end
			patterns = temps
		end

		# 確定済みのうち、11種類以上の数字を使うものは排除する
		defines.select{|define| define.size <= 10}
	end

	# パターンから作られる組み合わせの総数を計算する
	def self.comb(pattern)
		numer = MathEx.p(10, pattern.size)
		denom = pattern.uniq.inject(1){|sum, key| sum * MathEx.fact(pattern.count(key))}
		numer / denom
	end

	# パターンから作られる順列の総数を計算する
	def self.perm(pattern)
		numer = MathEx.fact(pattern.inject(:+))
		denom = pattern.inject(1){|sum, key| sum * MathEx.fact(key)}
		numer / denom * comb(pattern)
	end
end

# == main ==

n = 12

# パターンについて、獲得できる金額と作られる順列の総数を計算し、記録する
perms = Array.new(n + 1, 0)
Slot.patterns(n).each do |pattern|
	doller = pattern.max
	perms[doller] += Slot.perm(pattern)
end

# 期待値を計算して出力する
numer = perms.each_index.inject(0){|sum, doller| sum + perms[doller] * doller}
denom = perms.inject(:+)
puts numer.quo(denom).to_f

# n =  6 => 2.01966
# n = 12 => 3.10849098132

__END__

「パターン」 => 「組み合わせ」 => 「順列」 の順番に計算する。
パターンとは出目にあらわれる数字の数に着目して分類したものである。
たとえばn = 3のとき、以下がパターンのすべてである
	[4], [1, 3], [2, 2], [1, 1, 2], [1, 1, 1, 1]
いいかえるとパターンとは合計がnになる自然数の組である
次に組み合わせとはパターンを実際に数字を利用して表現したものである
たとえば上記の[1, 3]であれば、以下が組み合わせの総数である
	0111,0222,0333,0444,0555,0666,0777,0888,0999
	1000,1222,1333,1444,1555,1666,1777,1888,1999
	2000,2111,2333,2444,2555,2666,2777,2888,2999
	3000,3111,3222,3444,3555,3666,3777,3888,3999
	4000,4111,4222,4333,4555,4666,4777,4888,4999
	5000,5111,5222,5333,5444,5666,5777,5888,5999
	6000,6111,6222,6333,6444,6555,6777,6888,6999
	7000,7111,7222,7333,7444,7555,7666,7888,7999
	8000,8111,8222,8333,8444,8555,8666,8777,8999
	9000,9111,9222,9333,9444,9555,9666,9777,9888
最後に順列とは実際的な数字の並びである
たとえば0111からは以下の数字が作られる
	0111, 1011, 1101, 1110
以上のように、パターンからは組み合わせと順列を、それぞれもとめることができる
たとえば[1, 3]であれば 90 * 4 = 360個の数字がこのパターンに該当する
そして[1, 3]のパターンに属する数字の獲得金額は3ドルであることも簡単にわかる
問題はパターンを過不足なく列挙することだが、これも比較的容易にわかる