2

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?

Community
  • 1
  • 1
nowxue
  • 395
  • 1
  • 5
  • 17

2 Answers2

2

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.

false
  • 10,264
  • 13
  • 101
  • 209
  • 1
    Hi @false, thanks for answering. I'm very new to prolog, could you please elaborate on when you say "it is rather unusual to represent such sets explicitly, simply because Prolog can generate them so efficiently". How can I make prolog generate them? is my proposed solution ok? – nowxue Nov 08 '14 at 20:55
  • 1
    Above plus your definition is a correct solution. But it is rare that such sets are generated explicitly. That is, the list in `Subs` might be very large. On the other hand, `possiblesubset(S)` is easy to call directly **without** generating the entire set at once. – false Nov 08 '14 at 20:58
0

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.

Community
  • 1
  • 1
nowxue
  • 395
  • 1
  • 5
  • 17
  • Calling this relation `powerset/2` is a bit of a misnomer. Powerset would be: `powerset(M, P) :- bagof(S,seq_subseq(M,S),P).` – false Nov 08 '14 at 21:05
  • Yes, you're right. I'll change the code. Thanks for your help. – nowxue Nov 08 '14 at 21:10