[Haskell] Can anyone help me with partition numbers?
E. Zuurbier (Erik)
ezuurbier at adp.nl
Fri Nov 25 06:25:54 EST 2005
Doaitse,
For generate 4 this gives a.o. three equivalent solutions: [1,1,2],
[1,2,1] and [2,1,1]. I guess the ultimate idea would be to prune
permutations.
Regards Erik Zuurbier
Onderwerp: Re: [Haskell] Can anyone help me with partition numbers?
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