[Haskell-cafe] Can anyone help me with partition numbers?

[Fan Wu]

partition n = part n $ map (:[]) [1..n]
              where
                  part n [] = []
                  part n (x:xs)
                    |  s == n    = x: r
                    |  s > n     = r
                    |  otherwise = foldr (:) (part n $ map (:x) [h..n-1]) r
                    where
                       h = head x
                       s = sum x
                       r = part n xs


Main> partition 4
[[4],[2,2],[3,1],[2,1,1],[1,1,1,1]]   -- I guess the order doesn't matter here.


I myself is a newbie to Haskell. Every time I finished some code like
this I was amazed at the elegance and expressiveness of the language.
It's simply a different experience which you can't get from C/C++.

I hope you have spent enough time on it before you look at this,
otherwise you just missed some fun Haskell/homework/life has offered
you:-)

Cheers,
Fan


On 11/24/05, whoals (sent by Nabble.com) <lists at 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-Cafe forum at Nabble.com.
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>
>