CODEWITHSUNDEEP
haskellsubset-sum
user2948547
user2948547

Reputation: 336

Haskell get all the numbers whose sum is X

I need to create a function in haskell which receives a number and returns a list of lists, where the list has all combination of the numbers whose sum is the number received.

is dificult to explain so this is the example:

sum1 4 = [ [4], [3,1], [2,2], [1,3], [1,1,2], [1,2,1] , [2,1,1] ]

sum1 3 = [ [3], [2,1], [1,2], [1,1,1]

I need to do this with recursion and with comprehension list

EDIT

this is my code:

sum1 n = sum3 (sum2 1 (n-1) n)
sum2 x y n = if ((x+y)==n && x>0 && y>0) then [x,y]:sum2 (x+1) (y-1) n else []
sum3 [] = []
sum3 (x:xs) = sum4 x 1 : sum3 xs
sum4 [] t = []
sum4 (x:xs) t = if not (x == t) then (sum1 x) else x

And yes, this was an excesice of an exam but i don't know how to doit

Upvotes: 1

Views: 1195

Answers (1)

Random Dev
Random Dev

Reputation: 52280

I'll assume that this is homework (and a harder one IMO) so I will not spoil everything right now.

If you think about it you should see that there are basically two operations of how you can get from a list xs that sums to n to a list that sums to n+1:

  • you can add another 1
  • you can add 1 to some x in xs

so if you manage to implement both operations your task will be a lot easier.

The first one is not hard (hint (1:) is a function prepending an additional 1 to some list - now you have to map this...)

The second one is a bit harder although almost the same idea of divide&conquer will help you out.

Here is how I would start with it:

add1Somewhere :: Num a => [a] -> [[a]]
add1Somewhere [i] = [[i+1]]
add1Somewhere (i:is) = ???

(yes this is a partial function)

remarks:

  • as you can see below you don't really have to insert the additional 1 somewhere or choose any x in xs - using the first x in xs and prepending to the first place does suffice
  • the algorithm I'm hinting at will produce sometimes equal outcomes - for example if you have one [1,1] then you can end up at [2,2] later in two ways: [1,1] -> [2,1] -> [2,2] and [1,1] -> [1,2] -> [2,2] - those can be removed with Data.List.nub or if you change your algorithm to produce ordered/filtered results (don't produce [1,1] -> [1,2])
  • your example is missing things [1,1,1,1] and I honestly could not tell if the exercise hints at one such order
  • you probably should have a look at concatMap (or concat)
  • this is different from the algorithm @cirdec is hinting at (probably his is faster) - but the same problems with duplication applies if you insert an additional 1 at some place

solution

as it's some time and you said it's an old exam question I think it's ok to spoil it (don't read on if you don't want to)

So this is a possible solution (no care taken on any performance issue):

import Data.List (nub)

sum1 :: (Eq a, Num a) => a -> [[a]]
sum1 1 = [[1]]
sum1 n = nub $ concatMap add1Somewhere ns ++ map (1:) ns
  where ns = sum1 (n-1)

add1Somewhere :: Num a => [a] -> [[a]]
add1Somewhere [i] = [[i+1]]
add1Somewhere (i:is) = ((i+1):is) : map (i:) (add1Somewhere is)

please note that this uses concatMap and nub both of which might or might not be ok for this.

I hope you get the basic idea

obviously better solution

oops - I just noticed that you can get rid of all the problematic functions like concat and nub anyway as it's sufficient to just prepend a 1 or increment the very first list element - the recursion will provide all the needed permuations anyway (the different paths I mentioned are exactly the permutations) - there is a difference in the order though:

sum1 :: (Eq a, Num a) => a -> [[a]]
sum1 1 = [[1]]
sum1 n = map add1 ns ++ map prep1 ns
  where ns          = sum1 (n-1)
        prep1 is    = 1:is
        add1 (i:is) = (i+1):is

of course you can replace the map with a list-comprehension if you want

proof that this finds all permutations

by Induction on n (assuming only positive natural numbers)

for n=1 just notice that [1] is the only possible list

now assume that we find all permuations for n>0 and look at some list xs that will sum up to n+1 (obviously the list needs to be non-empty)

Now the first element x of xs = x:ys will be either 1 or >1

  • x=1 - in this case prep1 will provide xs because ys was found by our algorithm by induction (note that sum ys = sum xs - 1 = n)
  • x>1 - in this case (x-1):ys was found by our algorithm by induction and add1 will create xs (again because sum ((x-1):ys) = sum xs - 1 = n)

Upvotes: 4

Related Questions