[Haskell-cafe] Style and a problem
Daniel Fischer
daniel.is.fischer at web.de
Thu Sep 9 18:15:03 EDT 2010
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,
> \/\/
More information about the Haskell-Cafe
mailing list