CODEWITHSUNDEEP
prologsumsubset
PrinceOfBorgo
PrinceOfBorgo

Reputation: 590

List of subset sums Prolog

Given a list L of natural numbers I need to create a list containing the sums of the elements of all the subsets of L. For example if L=[1,3,6] I want to obtain the list [0,1,3,4,6,7,9,10].

I tried to use this code

subsetSums(List,Sums) :- findall(Sum,(subset(Sub,List),sum_list(Sub,Sum)),Sums).

but with the following query I get [0] as the only result instead of [0,1,2,3]

?- subsetSums([1,2],Sums).

Where am I wrong?

EDIT: I'm working on SWI Prolog and subset/2 should be a native predicate.

Upvotes: 1

Views: 692

Answers (1)

damianodamiano
damianodamiano

Reputation: 2662

As suggested in the comment, you have to write your own subset/2 predicate and then use findall/3 on this predicate, like this:

subset([], []).
subset([E|T], [E|T1]):-
  subset(T, T1).
subset([_|T], L):-
  subset(T, L).

subsetSums(List,Sums) :- 
    findall(S,(subset(List,Sub),sumlist(Sub,S)),Sums).

?- subsetSums([1,2],L).
L = [3, 1, 2, 0]
?- subsetSums([1,2,3],L).
L = [6, 3, 4, 1, 5, 2, 3, 0]

where the output of subset/2 is:

subset([1,2,3],L).
L = [1, 2, 3]
L = [1, 2]
L = [1, 3]
L = [1]
L = [2, 3]
L = [2]
L = [3]
L = []

Upvotes: 2

Related Questions