List comprehension: making lists of lists

问题:

hi im trying to make a function in haskell that takes a number a makes a partion of it using lists i.e. for number 4 it would create [[1,1,1,1],[1,1,2],[1,3],[2,2],[4]]. I was thinking of using list comprehension for this where it would create list x and then create further lists using numbers from [1...n] (n being the partition number I would want) where the sum of the list created would be equal to n.

The code I have created so far is-

partions (n:xs) = [[x|x<-[1...n], sum[x]==n]]|xs<-[1..]]

but obiviously it doesnt work, any suggestions?

thanks.

回答1:

I suggest trying recursion: To obtain the partitions of n, iterate over the numbers i = 1 to n, and recursively generate the partitions of (n-i), the base case being that the only partition of 1 is 1 itself, and the partition of 0 is the empty list.

回答2:

How about this...

import Data.List (nub, sort)

parts :: Int -> [[Int]]
parts 0 = []
parts n = nub $ map sort $ [n] : [x:xs | x <- [1..n`div`2], xs <- parts(n - x)]

Trying it:

*Main Control.Monad> forM [1..5] (print . parts)
[[1]]
[[2],[1,1]]
[[3],[1,2],[1,1,1]]
[[4],[1,3],[1,1,2],[1,1,1,1],[2,2]]
[[5],[1,4],[1,1,3],[1,1,1,2],[1,1,1,1,1],[1,2,2],[2,3]]

I think it's correct, if not efficient.

回答3:

I found it helpful to define an auxiliary function, partitionsCap, which does not let any of the items be larger than a given value. Used recursively, it can be used to only produce the monotonically decreasing results you want (i.e. no [1,3,1] when you already have [1,1,3]):

partitions :: Int -> [[Int]]
partitions n = partitionsCap n n

partitionsCap :: Int -> Int -> [[Int]]
partitionsCap cap n
    | n < 0  = error "partitions: negative number"
    | n == 0 = [[]]
    | n > 0  = [i : p | i <- [hi,hi-1..1], p <- partitionsCap i (n-i)]
               where hi = min cap n

---

At the heart of the algorithm is the idea that, when partitioning N, you take i from n down to 1, and prepend i to the partitions of n-i. Simplified:

concat [map (i:) $ partitions (n-i) | i <- [n,n-1..1]]

but wrong:

> partitions 3
[[3],[2,1],[1,2],[1,1,1]]

We want that [1,2] to go away. Hence, we need to cap the partitions we're prepending to so they won't go above i:

concat [map (i:) $ partitionsCap i (n-i) | i <- [hi,hi-1..1]]
where hi = min cap n

Now, to clean it up: that concat and map so close together got my attention. A little background: list comprehensions and the list monad are very closely related, and concatMap is the same as >>= with its arguments flipped, in the list monad. So I wondered: can those concat and map somehow turn into a >>=, and can that >>= somehow sweet-talk its way into the list comprehension?

In this case, the answer is yes :-)

[i : p | i <- [hi,hi-1..1], p <- partitionsCap i (n-i)]
where hi = min cap n

回答4:

I'm a little rusty with Haskell, but maybe the following code can guide you to find the solution.

parts :: Int -> Int -> [[Int]]
parts 0 p = [[]]
parts x p = [(y:ys) | y <-[p..x], ys <- (parts (x - y) y)]

And then you would have to call parts with x = n, and p = 1.

EDIT

I've fixed the base case when x equals 0 to return a list with a single item, being that item an empty list. Now it works fine :)