Can anyone help me with partition numbers?

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
9 messages Options
Reply | Threaded
Open this post in threaded view
|

Can anyone help me with partition numbers?

whoals
A partition of a positive integer n is a representation of n as the sum of any number of positive integral parts. For example, there are 7 partitions of the number 5: 1+1+1+1+1, 1+1+1+2, 1+1+3, 1+2+2, 1+4, 2+3 and 5. Define a function parts which returns the list of distinct partitions of an integer n. For example, parts 4 = [[1,1,1,1],[1,1,2],[1,3],[2,2],[4]].
Reply | Threaded
Open this post in threaded view
|

Re: Can anyone help me with partition numbers?

Jan van Eijck
On Thu, Nov 24, 2005 at 07:59:50AM -0800, whoals (sent by Nabble.com) wrote:
>
> A partition of a positive integer n is a representation of n as the sum of any number of positive integral parts. For example, there are 7 partitions of the number 5: 1+1+1+1+1, 1+1+1+2, 1+1+3, 1+2+2, 1+4, 2+3 and 5. Define a function parts which returns the list of distinct partitions of an integer n. For example, parts 4 = [[1,1,1,1],[1,1,2],[1,3],[2,2],[4]].
> --
> Sent from the Haskell - Haskell forum at Nabble.com:
> http://www.nabble.com/Can-anyone-help-me-with-partition-numbers--t612331.html#a1636283

> _______________________________________________
> Haskell mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/haskell

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])
 
Let's hope this does not spoil a computer lab assignment ;-)

Jan


--
Jan van Eijck                                EMAIL [hidden email]
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

_______________________________________________
Haskell mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell
Reply | Threaded
Open this post in threaded view
|

Re: Can anyone help me with partition numbers?

Tomasz Zielonka
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
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell
Reply | Threaded
Open this post in threaded view
|

Re: Can anyone help me with partition numbers?

S. Doaitse Swierstra-2
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
> [hidden email]
> http://www.haskell.org/mailman/listinfo/haskell

_______________________________________________
Haskell mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell
Reply | Threaded
Open this post in threaded view
|

Re: Can anyone help me with partition numbers?

Salvador Lucas
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
>> [hidden email]
>> http://www.haskell.org/mailman/listinfo/haskell
>
>
> _______________________________________________
> Haskell mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/haskell


_______________________________________________
Haskell mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell
Reply | Threaded
Open this post in threaded view
|

Re: Can anyone help me with partition numbers?

jerzy.karczmarczuk
In reply to this post by S. Doaitse Swierstra-2
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)]

Unless I am misled, this will generate the *unordered* partitions,
e.g., for n=7, 64 of them, not 15.


Jerzy Karczmarczuk
_______________________________________________
Haskell mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell
Reply | Threaded
Open this post in threaded view
|

RE: Can anyone help me with partition numbers?

E. Zuurbier (Erik)
In reply to this post by whoals
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
> [hidden email]
> http://www.haskell.org/mailman/listinfo/haskell

_______________________________________________
Haskell mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell
_______________________________________________
Haskell mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell
Reply | Threaded
Open this post in threaded view
|

Re: Can anyone help me with partition numbers?

Jan van Eijck
In reply to this post by Tomasz Zielonka
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 [hidden email]
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

_______________________________________________
Haskell mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell
Reply | Threaded
Open this post in threaded view
|

Re: Can anyone help...

jerzy.karczmarczuk
In reply to this post by jerzy.karczmarczuk
I apologize for the posting in which I mention the inadequacy of Doaitse
Swierstra partition program, it has been commented by others, and the thread
is obsolete. But my posting (issued immediately then) got delayed by the
moderator because of the schizoidal nature of my e-mail address... Sorry.

Jerzy Karczmarczuk
_______________________________________________
Haskell mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell