Mae向きなブログ

Mae向きな情報発信を続けていきたいと思います。

離散数学「数え上げ理論」

順列とか組み合せとか確率の問題は、答えを見るまでなんとなく自信が持てないこともあって、あまり面白いとも思わず得意でもなかったのですが、本書を読んで、少なくとも面白いと思えるようにはなったと思います。
どの章も良かったのですが、特に、分割数については、今までのもやもやとした感じから、すっきり理解できた感じがして、これだけでも本書を読んで良かったと思ってます。
以下は、分割数について忘れないように書き留めておきます。

事実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
(途中略)
15796476

real 0m23.894s
user 0m23.062s
sys 0m0.210s

  • NUM = 80で高速化の手法を使用した場合

$ time ruby partition.rb
(途中略)
15796476

real 0m3.947s
user 0m3.700s
sys 0m0.176s

高速化の手法の効果は目を見張るものがありました。