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.