[Haskell-cafe] Style and a problem

[Daniel Fischer]

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,
> \/\/