Prolog: expressing that two lists have at least two elements in common

Question

I am trying to find out if two lists overlap. The predicate I want to write takes two lists and returns true if the lists have at least two elements in common.

Sample queries with expected answer:

?- overlap([13,14,15], [17,18,13,19]).
false.

?- overlap([13,14,15], [14,17,13,18,16]).
true.

However, so far, I only got one element to work.

member(M, [M|_]).
member(M, [_|T]) :-
   member(M, T).

overlap(X, Y) :-
   member(M, X),
   member(M, Y).

?- overlap([a,b,c,d], [1,2,c,d]).

How can I make sure it checks two elements, not just one?

score 4 · Accepted Answer · edited May 23 '17 at 12:30

Another approach, very close to your code, would be to make sure that the two members are not the same:

overlap(X, Y) :-
    dif(A, B),
    member(A, X), member(A, Y),
    member(B, X), member(B, Y).

Since there is a comment asking for a more efficient way to do it, here is an altogether different approach, as in this answer to a very similar question.

overlap(N, X, Y) :-
    sort(Xs, SX),
    sort(Ys, SY),
    append(SX, SY, All), length(All, Len_all),
    sort(All, Sorted), length(Sorted, Len_sorted),
    Len_sorted =< Len_all - 2.

In simple words, since sort also removes all duplicates, you can count the number of duplicates in a list by comparing the length before and after sorting. Once you write the predicate in this fashion, you will also notice that you can generalize it a bit, so that it has two arguments: a list of lists, and a non-negative integer which is the number of elements shared among all lists:

overlap_n(LL, N) :-
    maplist(sort, LL, SLL), % sort all lists
    append(SLL, All), length(All, Len_all),
    sort(All, Sorted), length(Sorted, Len_sorted),
    N is Len_all - Len_sorted.

You can now express your original question as:

?- overlap_n([X, Y], N), N >= 2.

Nice, but can't this be a bit more efficient? – false Dec 10 '15 at 18:21 — false, Dec 10 '15 at 18:21
@false It could be a lot more efficient. – Dec 11 '15 at 07:12 — , Dec 11 '15 at 07:12

score 0 · Answer 2 · answered Dec 10 '15 at 07:13

If your Prolog has intersection/3, the shorter form could be:

overlap(X,Y) :- intersection(X,Y,[_,_|_]).

It will be inefficient for large, overlapping lists. Your approach is easily corrected and extended:

overlap(X,Y) :-
    select(A,X,Rx), select(A,Y,Ry),
    member(B,Rx), member(B,Ry).

I would add a cut at end to avoid multiple solutions...

Prolog: expressing that two lists have at least two elements in common

2 Answers2