[Haskell] Can anyone help me with partition numbers?

Salvador Lucas slucas at dsic.upv.es
Fri Nov 25 05:39:29 EST 2005


This does not work properly:

Main> generate 5
[[1,1,1,1,1],[1,1,1,2],[1,1,2,1],[1,1,3],[1,2,1,1],[1,2,2],[1,3,1],[1,4],[2,1,1,1],[2,1,2],[2,2,1],[2,3],[3,1,1],[3,2],[4,1],[5]]

You need to add something else:

parts 0 = [[]]
parts n = [m:p | m<-[1..n], p<-parts (n-m), (null p || m<=head p)]

Main> parts 5
[[1,1,1,1,1],[1,1,1,2],[1,1,3],[1,2,2],[1,4],[2,3],[5]]

Best,

Salvador.

Doaitse Swierstra wrote:

> Or (since we started to do someone's  homework anyway)
>
> generate 0 = [[]]
> generate n = [x:rest | x <- [1..n], rest <- generate (n-x)]
>
>
> Doaitse Swierstra
>
>
>
> On 2005 nov 25, at 10:29, 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
>>
>> _______________________________________________
>> Haskell mailing list
>> Haskell at haskell.org
>> http://www.haskell.org/mailman/listinfo/haskell
>
>
> _______________________________________________
> Haskell mailing list
> Haskell at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell




More information about the Haskell mailing list