離散数学「数え上げ理論」―「おみやげの配り方」から「Nクイーン問題」まで (ブルーバックス)
- 作者: 野崎昭弘
- 出版社/メーカー: 講談社
- 発売日: 2008/11/21
- メディア: 新書
- 購入: 14人 クリック: 104回
- この商品を含むブログ (34件) を見る
どの章も良かったのですが、特に、分割数については、今までのもやもやとした感じから、すっきり理解できた感じがして、これだけでも本書を読んで良かったと思ってます。
以下は、分割数について忘れないように書き留めておきます。
事実4-1
1) m < n のとき、p(m,n) = 0
2) m = n のとき、p(m,n) = 1
3) 任意の m >= 1 について、p(m,1) = 1
4) m > n の場合、
p(m,n) = p(m-n,n)+p(m-n,n-1)+p(m-n,n-2)+…+p(m-n,3)+p(m-n,2)+p(m-n,1)
事実4-2
m個の同じ品物をいくつかの同じ袋(何袋でもよい)に分ける仕方の数をp(m)とすると、
p(m)=p(m,1)+p(m,2)+…+p(m,m)
計算の高速化
1) p(m,2)=(m÷2)の端数切り捨て
2) p(m,3)=((m^3+3)÷12)の端数切り捨て
partition.rb
NUMの分割数を求めるスクリプトです。本書の例題では、NUM=8(8組のトランプ)でした。
# -*- coding: utf-8 -*- def partition m, n return 0 if m < n return 1 if m == n || n == 1 return m / 2 if n == 2 return (m * m + 3) / 12 if n == 3 ret = 0 [*1..n].each {|i| ret += partition(m - n, i) } ret end NUM = 8 arr = [] [*1..NUM].each {|n| arr << partition(NUM, n) } p arr p arr.reduce(:+)
実行結果
- NUM=8のとき
$ time ruby partition.rb
[1, 4, 5, 5, 3, 2, 1, 1]
22
高速化手法の効果を確かめるために、NUMを80にして高速化手法ありなしで実験してみました。
- NUM = 80で高速化の手法を使用しなかった場合
$ time ruby partition.rb
(途中略)
15796476real 0m23.894s
user 0m23.062s
sys 0m0.210s
- NUM = 80で高速化の手法を使用した場合
$ time ruby partition.rb
(途中略)
15796476real 0m3.947s
user 0m3.700s
sys 0m0.176s
高速化の手法の効果は目を見張るものがありました。