You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
20 lines
550 B
20 lines
550 B
module Stirling where
|
|
|
|
import Data.MemoTrie
|
|
|
|
-- Number of ways to partition n into k subsets
|
|
secondStirling :: Int -> Int -> Integer
|
|
secondStirling = memo2 ss where
|
|
ss n k = if k > n
|
|
then 0
|
|
else if n <= 6
|
|
then table !! n !! k
|
|
else (fromIntegral k) * secondStirling (n - 1) k + secondStirling n (k - 1)
|
|
table =
|
|
[ [1]
|
|
, [0, 1]
|
|
, [0, 1, 1]
|
|
, [0, 1, 3, 1]
|
|
, [0, 1, 7, 6, 1]
|
|
, [0, 1, 15, 25, 10, 1]
|
|
, [0, 1, 31, 90, 65, 15, 1] ]
|
|
|