On Fri, Sep 10, 2010 at 1:06 AM, Nils Schweinsberg wrote:

Something like this?

import Data.List

newList :: Int -> [[Int]] newList n = myNub [ l | l <- undefined -- not really sure how you want -- to generate these lists :) , sum l == sum [1..n] ]

myNub :: (Ord a) => [[a]] -> [[a]] myNub = nubBy (\a b -> sort a == sort b)

- Nils

So I've checked out this code, and it doesn't compile on ghci. My version, without the "undefined" portion is(which still doesn't work): import Data.List newList :: Int -> [[Int]] newList n = myNub [ l | l <- [1..n], sum l == sum [1..n] ] myNub :: (Ord a) => [[a]] -> [[a]] myNub = nubBy (\a b -> sort a == sort b) Maybe there's something in the syntax that I'm not quite getting... \/\/

Although it was phrased as one, it wasn't. If it were a homework question, wouldn't you think that I'd be trained to do it or have a TA to ask? But who said that you're accusing me of anything :) Thanks for your concern, Bulat. \/\/ On Fri, Sep 10, 2010 at 1:47 AM, Bulat Ziganshin wrote:

Hello Wanas,

Friday, September 10, 2010, 12:55:14 AM, you wrote:

...

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

you have very interesting questions. hopefully it was already answered at http://www.haskell.org/haskellwiki/Homework_help

-- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

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 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.