Partition function P: Difference between revisions

=={{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>