CODEWITHSUNDEEP
prologsubset
Shrp91
Shrp91

Reputation: 163

Proper Subset - Prolog

I am attempting to write a program that takes two lists as input and checks for proper subset. I started with:

proper([A],[]).
proper([],[A]).
proper([A|T1],[A|T2]) :- proper(T1,T2).

This works perfectly fine for inputs in the exact same order. for instance: 

?- proper([a,b,c],[a,b,c,d]).
Yes

But doesn't for inputs such as:

?- proper([a,b,c],[b,d,a,c]).
No

After looking through the site I found this previously asked question:

Subset function in prolog

Which lead me to modify my code as such:

proper([A],[]).
proper([],[A]).
proper([A|T1],[A|T2) :- member(A,T2), proper(T1,T2).
proper([H1|T1], [H2|T2]) :- \+ member(H1, T2).

This works fine for subsets but not for proper subsets. Which I think my problem is arising from my understanding of how the second clause of proper/4 works. Any and all help is greatly appreciated.

Edit:

Realized I was trying to determine if the first list was a proper subset of the second and the second was a proper subset of the first. Cleaned up the code to be more precise.

proper([],_).
proper([A|T1],[A|T2) :- member(A,T2), proper(T1,T2).
proper([H1|T1], [H2|T2]) :- \+ member(H1, T2).

Upvotes: 6

Views: 1098

Answers (1)

Shon
Shon

Reputation: 4098

If I understand correctly, the first two declarations in your last attempt would mean that, both a list with 1 element is a proper subset of an empty list (false), and that an empty list is a proper subset of a list with one element (true); the first one should be problematic, because proper([1], []) will succeed as well as proper([],[1]), but the proper subset relation is asymmetric.

I believe the reason that your second attempt doesn't filter out identical subsets is that you have no declaration that requires A to be smaller than B.

Here are some possible solutions I came up with. I use smaller_set/2 a couple times for increased clarity and concision.

smaller_set(A, B) :-
    length(A, LA),
    length(B, LB),
    LA < LB.

def_proper_subset/2 tries to capture the standard definition of a subset.

def_proper_subset(A, B) :-
    smaller_set(A, B),                    % if A < B then there's some _e in B that isn't in A.
    forall(member(_e, A), member(_e, B)).

An example with recursive definition, based on removeing each matching element of A and B. It assures that A < B by only succeeding if A runs out of elements before B.

rec_proper_subset1([], [_|_]).
rec_proper_subset1([_e|A], B) :-
    select(_e, B, C),            % C is B with _e removed. Only true if _e is in B.
    rec_proper_subset1(A, C).

This one uses an auxiliarry predicate to check membership once the main predicate has already assured that A < B.

rec_proper_subset2(A, B) :-
    smaller_set(A, B),
    rec_proper_subset2_(A, B).

rec_proper_subset2_([], _).
rec_proper_subset2_([_e|A], B) :-
    member(_e, B),
    rec_proper_subset2_(A, B).

Edit:

  • You'll need to use list_to_set/2, sort/2, or something similar if you want to be sure that your lists don't have any duplicate elements. But these kinds of solutions will also work to find sub lists.
  • I think def_proper_subset/2 is a kind of crappy solution, because it will only work to check that A is a subset of B but can't generate a subset of B in A. The other two are able to thought.

(I screwed up and forgot to include the ground definition for rec_proper_subset2/2, but I have now fixed it).

Upvotes: 2

Related Questions