CODEWITHSUNDEEP
prologsubset-sum
rares.urdea
rares.urdea

Reputation: 660

Get all subsets that sum up to a value N in Prolog

This is the problem statement:

Given a list of integers L and an integer S, generate all sublists whose elements add up to S.

This is my solution:

domains
        list=integer*
        clist=list*
predicates
        sum(list,integer)
        check(clist,clist,integer)
        gensub(list,list)
        getsub(list,clist,integer)
clauses
        %gets all possible subsets with gensub and findall, binds them to
        %and then checks the subsets to see if the elements add up to S
        %and adds the correct ones to Rez.
        %Goal example: getsub([1,2,5,6],X,7)
        getsub([], [], _).
        getsub(L, Rez, S):-
                findall(LR, gensub(L,LR), X),
                check(X, Rez, S).

        %generates all possible subsets of the given set
        gensub([], []).
        gensub([E|Tail], [E|NTail]):-
                gensub(Tail, NTail).
        gensub([_|Tail], NTail):-
                gensub(Tail, NTail).

        %checks if the sum of the elements of a list is S
        sum([], S):-S=0.
        sum([H|T], S):-
                N=S-H,
                sum(T, N).

        %checks if each sublist of a given list of lists, has the sum of elements S
        check([], [], S).
        %the LR variable here gives a warning after entering the goal
        check([H|T], [H|LR], S):-
                sum(H, S).

So after I run it and I'm asked for the Goal, I try to do getsub([1,2,5,6],X,7) so that I get all subsets whose elements add up to 7, but I get a No Solution, and a warning on the LR variable in the check clause, the variable is not bound. I'm not sure what I'm doing wrong or if there is an easier solution to this. Any help is appreciated.

Upvotes: 3

Views: 3475

Answers (2)

repeat
repeat

Reputation: 18726

In this answer we use :

:- use_module(library(clpfd)).

To get to all possible sublists, we use sublist_of/2:

sublist_of(Sub,List) :-
   list_sub(List,Sub).

sublist_of/2 is based on auxiliary predicate list_sub/2:

list_sub([]    ,[]).
list_sub([_|Xs],Ys) :-
   list_sub(Xs,Ys).
list_sub([X|Xs],[X|Ys]) :-
   list_sub(Xs,Ys).

Let's put it together!

list_sublist_sum(Xs,Zs,Sum) :-
   sublist_of(Zs,Xs),
   sum(Zs,#=,Sum).

Sample query:

?- list_sublist_sum([3,34,4,12,5,2],Zs,9).
  Zs = [4,5]
; Zs = [3,4,2]
; false.

Upvotes: 2

CapelliC
CapelliC

Reputation: 60004

I think your last procedure should read

%checks if each sublist of a given list of lists, has the sum of elements S
check([], [], _).
%the LR variable here gives a warning after entering the goal
check([H|T], [H|LR], S):-
    sum(H, S),
    !, check(T, LR, S).
check([_|T], LR, S):-
    check(T, LR, S).

and then, some note:

  • why generate all subsets, then filter out ? 'push' the test inside findall, it's easier and faster
  • you have a sum/2 predicate that could be much more useful if it does what it says to do. Here is it:

--

% sum elements of a list
sum([], 0).
sum([H|T], S):-
    sum(T, N),
    S is N+H.

(to be true, I tested using this one, getting [[1,6],[2,5]])

Upvotes: 3

Related Questions