CODEWITHSUNDEEP
prolog
nowxue
nowxue

Reputation: 425

Prolog find all subsets matching condition

I'm trying to solve a problem in SWI-Prolog. I have a list of suitable elements (constants) obtained with.

suitables(L) :- setof(X, isSuitable(X), L).

Each element from above has a score via a functor, and I need all the subsets that have a score > 10. I know how to get the score sum:

scoreSum([], 0).
scoreSum([H,T], Tot) :- getScore(H,F),scoreSum(T, Rest), Tot is F+Rest.

And the condition can be expressed like this:

cond(L) :- scoreSum(L, R), R > 10.

How do I get all the subsets matching the given condition? I can get the subsets based on the answer here, but how do I iterate over that result to get only the subsets matching the condition?

Upvotes: 2

Views: 1669

Answers (2)

nowxue
nowxue

Reputation: 425

I think I found the solution I needed, although I'm not sure if it's efficient or the recommended way. Provided the following functors:

isSuitable(X) :- ...

scoreSum([], 0).
scoreSum([H,T], Tot) :- getScore(H,F),scoreSum(T, Rest), Tot is F+Rest.

And the condition:

cond(L) :- scoreSum(L, R), R > 10.

I can get only the sets that meet the given condition:

suitables(L) :- setof(X, isSuitable(X), S), setof(R, (powerset(S, R), cond(R)),L).

Where powerset gives me all the subsets of the given set:

powerset([], []).
powerset([_|T], P) :- powerset(T,P).
powerset([H|T], [H|P]) :- powerset(T,P).

So instead of getting all the combinations, I've based on this question to get all sets of the list.

Upvotes: 0

false
false

Reputation: 10102

Provided scoreSum/2 starts with scoreSum([H|T], Tot) :- ...

seq_subseq([], []).
seq_subseq([_|Es], Fs) :-
   seq_subseq(Es, Fs).
seq_subseq([E|Es], [E|Fs]) :-
   seq_subseq(Es, Fs).

possiblesubset(S) :-
   suitables(L),
   seq_subseq(L, S),
   cond(S).

?- setof(S, possiblesubset(S), Subs).

?- setof(S, (suitables(L), seq_subseq(L,S), cond(S)), Subs).  % No L^ needed ; there is only one L.

However, it is rather unusual to represent such sets explicitly, simply because Prolog can generate them so efficiently.

Upvotes: 2

Related Questions