On Thursday 09 September 2010 22:55:14, 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 better to not create equivalent lists from the beginning. For n = 12, for example, there are almost 500 million (479001600) permutations of [1 .. 12], that's a lot of wasted work if you create them all and throw away all but one. Assuming that the list elements should be positive (or at least non- negative), what you want is to create the partitions of a target sum with a given length. Such a partition can be represented as a list of pairs (number, multiplicity) with the properties a) the sum of the multiplicities is the target length sum (map snd partition) == targetLength b) the sum of (number * multiplicity) is the target sum sum [n * m | (n,m) <- partition] == targetSum Such a representation is unique if you demand that the numbers (map fst partition) form a strictly decreasing (or increasing, but decreasing is simpler to construct) list and all multiplicities are strictly positive. So you want a function buildPartitions :: Integer -> Integer -> Integer -> [[(Integer,Integer)]] buildPartitions targetSum targetLength maxNumber should create the list of all essentially different partitions of targetSum into exactly targetLength positive (non-negative) numbers not greater than maxNumber. There are two sorts of such partitions, those containing maxNumber and those which don't, hence buildPartitions targetSum targetLength maxNumber = listOne ++ listTwo where listTwo = buildPartitions targetSum targetLength (maxNumber - 1) and listOne is constructed per - for all multiplicities mul from 1 to some limit - for all partitions part of (targetSum - mul*maxNumber) with length (targetLength - mul) into positive numbers < maxNumber - prefix (maxNumber, mul) to part Of course, for there to be any such partitions, some conditions have to be met: targetSum <= targetLength*maxNumber targetSum >= targetLength (if the numbers have to be strictly positive) With these conditions in mind for the recursive call, you can efficiently generate the list of all essentially different partitions via buildPartitions targetSum targetLength maxNumber = [(maxNumber, mul) : part | mul <- [1 .. maxMul] , part <- buildPartitions newSum newLength newMax] ++ buildPartitions targetSum targetLength (maxNumber-1) with appropriate values of maxMul and newMax (newMax can often be smaller than maxNumber-1) and a few cases to end the recursion (when no or only one partition is possible). Then you have to flatten the [(Integer, Integer)] lists into [Integer] lists, for example per flatten ps = [n | (n,m) <- ps, _ <- [1 .. m]]
b-2) I think that's too much questions, but I want to get the hang of this quickly (it was kickass for the few things I've tried out).
Thanks, \/\/