Anonymous user
Partition function P: Difference between revisions
→{{header|Haskell}}: added solution
No edit summary |
(→{{header|Haskell}}: added solution) |
||
Line 657:
Computation time in ms: 26
</pre>
=={{header|Haskell}}==
<lang haskell>{-# language DeriveFunctor #-}
------------------------------------------------------------
-- memoization utilities
data Memo a = Node a (Memo a) (Memo a)
deriving Functor
memo :: Integral a => Memo p -> a -> p
memo (Node a l r) n
| n == 0 = a
| odd n = memo l (n `div` 2)
| otherwise = memo r (n `div` 2 - 1)
nats :: Memo Int
nats = Node 0 ((+1).(*2) <$> nats) ((*2).(+1) <$> nats)
------------------------------------------------------------
-- calculating partitions
partitions :: Memo Integer
partitions = partitionP <$> nats
partitionP :: Int -> Integer
partitionP n
| n < 2 = 1
| otherwise = sum $ zipWith (*) signs terms
where
terms = [ memo partitions (n - i)
| i <- takeWhile (<= n) ofsets ]
signs = cycle [1,1,-1,-1]
ofsets = scanl1 (+) $ mix [1,3..] [1,2..]
where
mix a b = concat $ zipWith (\x y -> [x,y]) a b
main = print $ partitionP 6666</lang>
<pre>*Main> partitionP <$> [1..10]
[1,2,3,5,7,11,15,22,30,42]
*Main> partitionP 100
190569292
*Main> partitionP 1000
24061467864032622473692149727991
*Main> partitionP 6666
193655306161707661080005073394486091998480950338405932486880600467114423441282418165863</pre>
=={{header|J}}==
| |||