[Haskell] Can anyone help me with partition numbers?
Tomasz Zielonka
tomasz.zielonka at gmail.com
Fri Nov 25 04:29:48 EST 2005
On Thu, Nov 24, 2005 at 05:52:23PM +0100, Jan van Eijck wrote:
> Like so:
>
> generatePs :: (Int,[Int]) -> [[Int]]
> generatePs (n,[]) = [take n (repeat 1)]
> generatePs (n,(x:xs)) =
> (take n (repeat 1) ++ (x:xs)) : generatePs (pack (x-1) ((n+x),xs))
> where
> pack :: Int -> (Int,[Int]) ->(Int,[Int])
> pack 1 (m,xs) = (m,xs)
> pack k (m,xs) = if k > m then pack (k-1) (m,xs)
> else pack k (m-k,k:xs)
>
> parts :: Int -> [[Int]]
> parts n | n < 1 = error "part: argument <= 0"
> | n == 1 = [[1]]
> | otherwise = generatePs (0,[n])
How about a shorter version?
part :: Integer -> [[Integer]]
part = gen 1
where
gen m 0 = [[]]
gen m n = [ x:xs | x <- [m..n], xs <- gen x (n - x) ]
Best regards
Tomasz
More information about the Haskell
mailing list