[Haskell-cafe] Style and a problem

[Wanas]

I should've mentioned that the maximum number in such a list is n. That's
why it stuck me as 'a bit' inexpensive.

\/\/

On Fri, Sep 10, 2010 at 5:02 AM, Richard O'Keefe <ok at cs.otago.ac.nz> wrote:

>
> On Sep 10, 2010, at 8:55 AM, Wanas wrote:
>
> > Hey all,
> >
> > So I have a two part question (I'm new to haskell, so you can throw all
> your mugs at me).
> >
> > a) I want to write a function that generates lists of lists of size $n$.
> All having the property that sum lst = sum [1..n].
> > a-1) After that, I want to remove all permutations. My idea of doing this
> is to get all lists from the first function and create a new list with the
> property that "if sorted list A is not in the list, add it."
>
> It's not completely clear to me what you want.
> Here's my take on it:
>        S0 = {L | L is a list of positive integers and sum L = n}
>        L1 ~~ L2 iff L2 is a permutation of L1
> You want to enumerate S0/~~.
>
> Staring at this for a bit, what you want is
>        ENUMERATING THE PARTITIONS OF AN INTEGER.
> Look this up in almost any combinatorics book and you will find an
> algorithm that you can adapt.  There's stuff in Knuth, AOCP, Vol 4,
> for example.  A good reference is "The Theory of Partitions", by
> G. E. Andrews, Cambridge University Press, 1998.
>
> Rung-Bin Lin has reported in "Efficient Data Structures for Storing
> the Partitions of an Integer" on a data structure for representing
> all the partitions of an integer n in O(n**2) space, taking O(n**2)
> time to construct it, so a list of lists might not be the best way
> to do it in Haskell.
>
> What you want to do is to generate the partitions in a canonical
> order with no duplicates in the first place.  Something along these
> lines:
>
> the partiions of n are
>    the partitions of n into pieces no bigger than n with [] appended.
>
> the partitions of n into pieces no bigger than k with xx appended are
>    the partitions of n-k into pieces no bigger than k with k::xx appended
>  followed by
>    the partitions of n into pieces no bigger than k-1 with xx appended
>
> *with* some termination clauses which I haven't shown.
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20100910/39f9e1d2/attachment.html