List of subset sums Prolog

Question

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.

Where is subset/2 defined? Is it really subset(Subset, List) or should it be subset(List, Subset)? — lurker
Sorry, I haven't specified that I'm working on SWI Prolog and it should be subset(Subset,List) according to the documentation swi-prolog.org/pldoc/man?predicate=subset/2 — PrinceOfBorgo
It doesn't work even changing the code to subsetSums(List,Sums) :- findall(Sum,(list_to_set(List,Set),subset(Sub,Set),sum_list(Sub,Sum)),Sums). — PrinceOfBorgo
subset/2 only checks the property. Both params are input (+). — Tomas By
Even if subset/2 did what you wanted, sum_list/2 does not work on sets. Just write your own list_subset/2 predicate. It's easy. Or at least you can find it half a dozen places here on SO. — lurker

damianodamiano damianodamiano · Accepted Answer · 2018-01-18T20:50:52

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 = []

List of subset sums Prolog

1 Answers