Anonymous user
Stirling numbers of the first kind: Difference between revisions
added Haskell
m (Simplified code) |
(added Haskell) |
||
Line 473:
which has 158 digits.
</pre>
=={{header|Haskell}}==
Using library: data-memocombinators for memoization
<lang haskell>import Text.Printf (printf)
import Data.List (groupBy)
import qualified Data.MemoCombinators as Memo
sterling1 :: Integral a => a -> a -> a
sterling1 = Memo.memo2 Memo.integral Memo.integral f
where
f n k
| n == 0 && k == 0 = 1
| n > 0 && k == 0 = 0
| k > n = 0
| otherwise = sterling1 (pred n) (pred k) + pred n * sterling1 (pred n) k
main :: IO ()
main = do
printf "n/k"
mapM_ (printf "%10d") ([0..12] :: [Int]) >> printf "\n"
mapM_ (\row -> printf "%3d" (fst $ head row) >>
mapM_ (printf "%10d" . uncurry sterling1) row >> printf "\n") table
print $ maximum [sterling1 100 n | n <- [1..100]]
where
table :: [[(Int, Int)]]
table = groupedByX $ (,) <$> [0..12] <*> [0..12]
groupedByX = groupBy (\a b -> fst a == fst b)</lang>
Or library: monad-memo for memoization. Seems to be a few milliseconds slower.
<lang haskell>{-# LANGUAGE FlexibleContexts #-}
import Text.Printf (printf)
import Data.List (groupBy)
import Control.Monad.Memo (MonadMemo, memo, startEvalMemo, for2)
sterling1 :: (Integral n, MonadMemo (n, n) n m) => n -> n -> m n
sterling1 n k
| n == 0 && k == 0 = pure 1
| n > 0 && k == 0 = pure 0
| k > n = pure 0
| otherwise = do
f1 <- for2 memo sterling1 (pred n) (pred k)
f2 <- for2 memo sterling1 (pred n) k
pure (f1 + pred n * f2)
sterling1Memo :: Integral n => n -> n -> n
sterling1Memo n k = startEvalMemo $ sterling1 n k
main :: IO ()
main = do
printf "n/k"
mapM_ (printf "%10d") ([0..12] :: [Int]) >> printf "\n"
mapM_ (\row -> printf "%3d" (fst $ head row) >>
mapM_ (printf "%10d" . uncurry sterling1Memo) row >> printf "\n") table
print $ maximum [sterling1Memo 100 n | n <- [1..100]]
where
table :: [[(Int, Int)]]
table = groupedByX $ (,) <$> [0..12] <*> [0..12]
groupedByX = groupBy (\a b -> fst a == fst b)</lang>
{{out}}
<pre>n/k 0 1 2 3 4 5 6 7 8 9 10 11 12
0 1 0 0 0 0 0 0 0 0 0 0 0 0
1 0 1 0 0 0 0 0 0 0 0 0 0 0
2 0 1 1 0 0 0 0 0 0 0 0 0 0
3 0 2 3 1 0 0 0 0 0 0 0 0 0
4 0 6 11 6 1 0 0 0 0 0 0 0 0
5 0 24 50 35 10 1 0 0 0 0 0 0 0
6 0 120 274 225 85 15 1 0 0 0 0 0 0
7 0 720 1764 1624 735 175 21 1 0 0 0 0 0
8 0 5040 13068 13132 6769 1960 322 28 1 0 0 0 0
9 0 40320 109584 118124 67284 22449 4536 546 36 1 0 0 0
10 0 362880 1026576 1172700 723680 269325 63273 9450 870 45 1 0 0
11 0 3628800 10628640 12753576 8409500 3416930 902055 157773 18150 1320 55 1 0
12 0 39916800 120543840 150917976 105258076 45995730 13339535 2637558 357423 32670 1925 66 1
19710908747055261109287881673376044669240511161402863823515728791076863288440277983854056472903481625299174865860036734731122707870406148096000000000000000000</pre>
=={{header|J}}==
| |||