What's with subset/2?

Help!
1

I’m using: SWI-Prolog version SWISH

I want the code to: find bindings for subsets

But what I’m getting is: only one set of bindings, and it’s not even a set

My code looks like this:

?- subset([A,B],[1,2,3]).
A = B, B = 1

No buttons in the results window to try more bindings.
I would expect [1,2], [1,3], etc.

?- trace,subset([A,B],[1,2,3]).
Call:lists:subset([_4884, _4888], [1, 2, 3])
 Exit:lists:subset([1, 1], [1, 2, 3])
A = B, B = 1
2

So, the reason you’re not getting the results you’re hoping for is that, by the docs, subset/2 (and its cousin, ord_subset/2) only operates in the (+, +) mode, i.e. with both parameters as inputs. Generation shouldn’t be too tough, though:

any_subset([], []).
any_subset([H|T], Subset) :-
    any_subset(T, Subset)
    ;
    Subset = [H|Sub1],
    any_subset(T, Sub1).

(I swapped the order of the parameters, but only because of a SWI-Prolog-specific optimization. That’s also why this predicate has two clauses, not three.)

1 Like
3

I was wondering what those doohickies were. Thank you. :smiley:

How about this:

is_subset([],_).
is_subset([H|T],Set) :-
  member(H,Set),
  delete(Set,H,Remainder),
  is_subset(T,Remainder).

Or with select(H,Set,Remainder) instead of delete(Set,H,Remainder).

4

That’s a decent way to do it if you’re looking for all permutations, rather than combinations, yes! You’re correct that select/3 is a better predicate to use than delete/3 (I actually had to look up delete/3 in the docs, because it’s not a commonly-used predicate), but I’ll take it one step further: you can replace both the calls to member/2 and delete/2 with a single call to select(H, Set, Remainder). Notice that the docs for select/3 specifies the mode as (?, ?, ?) - that’s the ideal for a Prolog predicate, actually, as it specifies that any of the arguments can be used as input or output.

Incidentally, that’s also the reason why most predicate documentation is phrased with the almost Jeopardy-esque “Is true when…” preface rather than using imperative language like “Removes Elem from List1”, even when that requires jumping through some grammatical hoops. In Prolog, you ideally aren’t specifying the process so much as the solution. (Of course, realistically that’s not always the case, but the ideal still holds.)

I’ll offer you another solution, though - not because I think it’s better so much as it’s just fun:

is_subset(Subset, Set) :-
    permutation(Set, Perm),
    prefix(Subset, Perm).
1 Like
5

I think that this has been already discussed here in the context of ord_subset/2. As long as you represent the set as list, the same considerations apply. For any list without repetitions the set of subsequences of the list is the same as the set of subsets. The gist of it (excerpt from the linked post):

list_subseq_1([], _).
list_subseq_1([X|Xs], L) :-
    append(_, [X|Rest], L),
    list_subseq_1(Xs, Rest).

So, for a subsequence you can use append/3, instead of member/2 and select/3 or delete/3 and so on.

For your example, I get:

?- list_subseq([1,2,3], [A,B]).
A = 1, B = 2 ;
A = 1, B = 3 ;
A = 2, B = 3 ;
false.
1 Like
6

That’s awesome. It’s amazing how sneaky you can be with Prolog. :grin: :grin: :grin: