9

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.

hlovdal
  • 26,565
  • 10
  • 94
  • 165
dave
  • 91
  • 1
  • 4

4 Answers4

4

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.

cadolphs
  • 9,014
  • 1
  • 24
  • 41
3

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.

Tom Crockett
  • 30,818
  • 8
  • 72
  • 90
2

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 :)

Fede
  • 3,928
  • 1
  • 20
  • 28
  • maybe I'm missing something, but I get an error: Couldn't match expected type t1->t against inferred type [[Int]]. In the expression: parts 4 1. In the definition of 'it': it = parts 4 1 – Matt Ellen Nov 19 '10 at 16:47
  • @Matt I'm no expert, but I think you may be using `it` in another context, and the type inference for `it` doesn't match with `[[Int]]`. I've called `parts 4 1` using WinHugs and the output was exactly as @dave's example – Fede Nov 19 '10 at 17:37
  • You shouldn't define 'it'. 'it' is always the result of the last calculation in GHCi. – nomen Dec 11 '12 at 00:38
2

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
Joey Adams
  • 41,996
  • 18
  • 86
  • 115