[Haskell] Can anyone help me with partition numbers?

[Jan van Eijck]

On Fri, Nov 25, 2005 at 10:29:48AM +0100, Tomasz Zielonka wrote:
> 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
> 

Brilliant! 

Jan 

-- 
Jan van Eijck                                EMAIL jve at cwi.nl
CWI, PO Box 94079, 1090 GB Amsterdam, NL     phone +31-20-5924052 (work)      
                                                   +31-20-6250735 (home)
WWW   http://www.cwi.nl/~jve                 fax   +31-20-5924200