[Haskell-cafe] Style and a problem

[Richard O'Keefe]

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.