Как определить, имеют ли два списка один и тот же элемент в прологе?

Question

Как определить, имеют ли два списка один и тот же элемент в прологе? Если у меня есть два списка A и B, я хочу знать, имеют ли они один и тот же элемент.

Answer 1

Вам нужно написать предикат. Возможно, вы найдете встроенный пролог member/2 полезным.

Трудно сказать больше, не дав ответа. Просто подумай об этом немного. Вы получите это.

Answer 2

Как насчет использования intersection/3?

doesIntersect(X,Y) :-
    intersection(X,Y,Z),
    dif(Z,[]).

Если intersection/3 создает пустой список, тогда списки не имеют ничего общего, и результат ложен.

intersection/3 вызовы member/2 рекурсивно:

intersection([X|Tail],Y,[X|Z]) :-
    member(X,Y),
    intersection(Tail,Y,Z).
intersection([X|Tail],Y,Z) :-
    \+ member(X,Y),
    intersection(Tail,Y,Z).
intersection([],_,[]).

источник.

Answer 3

Мы начнем с чистой реализации, основанной на встроенном предикате member/2:

common_member(Xs,Ys) :-
   member(E,Xs),
   member(E,Ys).

Примеры запросов:

?- common_member([1,2,3],[1]).
  true
; false.

?- common_member([1,2,3],[4]).
false.

?- common_member([1,2,3],[2,3,1]).
  true
; true
; true
; false.

Декларативно, приведенный выше код в порядке. Тем не менее, он оставляет за собой бесполезные точки выбора при успехе. Кроме того, мы получаем избыточные ответы, если в обоих списках присутствует более одного элемента.

Можем ли мы улучшить вышеуказанные аспекты эффективности, оставаясь логически чистыми? Да!

Но как? Используя if_/3 вместе с утвержденным тестовым предикатом memberd_t/3!

common_memberd([X|Xs],Ys) :-
   if_(memberd_t(X,Ys), true, common_memberd(Xs,Ys)).

Давайте снова запустим примеры запросов, на этот раз с common_memberd/2:

?- common_memberd([1,2,3],[1]).
true.

?- common_memberd([1,2,3],[4]).
false.

?- common_memberd([1,2,3],[2,3,1]).
true.

Избыточные ответы были исключены, а последующие запросы делают это детерминировано.

Обратите внимание, что common_memberd/2 чисто, поэтому мы получаем надежные ответы даже для довольно общих запросов!

?- common_memberd([1,2,3],[A,B]).
      A=1
; dif(A,1),                         B=1
;               A=2 ,           dif(B,1)
; dif(A,1), dif(A,2),                         B=2
;                         A=3 , dif(B,1), dif(B,2)
; dif(A,1), dif(A,2), dif(A,3),                     B=3
; false.

Answer 4

Вы можете начать с создания предиката differs/2, который проверяет, не является ли какой-либо из элементов в списке A членом списка B. Если вы можете найти элемент на A, который удовлетворяет этому условию, то вы можете подтвердить, что A не содержится в B. Это на самом деле проще, если попытаться проверить, что каждый элемент A присутствует в B.
Используя встроенный предикат member/2, differs/2 будет выглядеть так:

differs(T, Q):- 
         member(X,T), 
         not( member(X, Q)). 

Теперь, чтобы доказать, что оба списка содержат одни и те же элементы, вам просто нужно убедиться, что они не differs. Используя то же имя предиката, что и @repeat (любопытно, а кто теперь повтор?), Это мой предикат common_memberd\2:

common_memberd(T, Q):- 
                not( differs(T, Q)), 
                not( differs(Q, T)).

Consult:

?- common_memberd( [2,3,4,1], [3, 1,4,2]).  
   true.  
?- common_memberd( [2,3,1,5], [3, 1,4,2]).  
   false.

Примечание : Это решение работает независимо от порядка элемента, либо они дублированы, либо нет.

Answer 5

Дайте мне знать, если это то, что вы ищете:

same(T, Q) :- any(T, Q), !; any(Q, T), !.

any([X|_], [X,_]):- !.
any([X|T], Q) :- member(X, Q), !; any(T, Q), !.

Если вы обратитесь к нему:

?- same([1,2,3,4], [3]).
true.

?- same([1,2,3,4], [4]).
true.

?- same([1], [1,4]).
true.

?- same([1,4], [1]).
true.