在序言中查找两个列表之间没有重复项的交集

Question

我正在使用 Prolog，我试图找到两个列表之间的交集或公共元素，结果不应包含重复项。此外，应处理具有不同长度的列表的情况。谓词的结果应该如下：


?-no_duplicates_intersection([a,v,a,c],[a,a,a,a,a],L).
L = a.

实际上，我发现了一两个解决相同问题的问题，但答案太长了。我想知道是否有使用以下谓词的更直接和更简单的方法，returns 两个具有重复项的列表之间的交集：


intersection_with_dulpicates([], [], []).            
intersection_with_dulpicates([],M,[]).
intersection_with_dulpicates([X|Y],M,[X|Z]):- 
                     member(X,M),
                     intersection_with_dulpicates(Y,M,Z).
intersection_with_dulpicates([X|Y],M,Z):- 
                     \+member(X,M),
                     intersection_with_dulpicates(Y,M,Z).

Answer 1

利用 built-in 排序（也删除重复项）：

intersection_without_duplicates(Lst1, Lst2, Intersection) :-
    % Sort and remove duplicates from both
    % The built-in sort is quick
    sort(Lst1, Lst1Sorted),
    sort(Lst2, Lst2Sorted),
    intersect_sorted(Lst1Sorted, Lst2Sorted, Intersection).

intersect_sorted([], _Lst2Sorted, []).
intersect_sorted([H|T], LstSorted, Intersection) :-
    (   member_listsorted(H, LstSorted)
    ->  Intersection = [H|Intersection0]
    ;   Intersection0 = Intersection
    ),
    intersect_sorted(T, LstSorted, Intersection0).

member_listsorted(H, LstSorted) :-
    member_listsorted_(LstSorted, H).

member_listsorted_([H|T], Elem) :-
    (   H @< Elem
    ->  member_listsorted_(T, Elem)
    ;   H = Elem
    ).

swi-prolog 中的示例输出：

?- time(intersection_without_duplicates([a, b, c, d, b, c, d], [b, c, b, c, d],
I)).
% 31 inferences, 0.000 CPU in 0.000 seconds (89% CPU, 586277 Lips)
I = [b,c,d].

?- numlist(1, 10000, Lst1), numlist(5000, 12345, Lst2), time((intersection_without_duplicates(Lst1, Lst2, Intersection))).
% 25,060,003 inferences, 1.313 CPU in 1.297 seconds (101% CPU, 19090034 Lips)

与@TessellatingHeckler 的建议的性能比较：

?- numlist(1, 10000, Lst1), numlist(5000, 12345, Lst2), time((intersection(Lst1, Lst2, Both), sort(Both, Answer))).
% 35,001 inferences, 2.193 CPU in 2.167 seconds (101% CPU, 15957 Lips)

Answer 2

按照intersection_with_dulpicates的设计你可以试试

no_duplicates_intersection([], _L2, []).

no_duplicates_intersection([X|Y],L, Intersection):-
   no_duplicates_intersection(Y,L,Cur_intersection),
   ( (member(X, Cur_intersection); \+ member(X,L))
     -> Intersection = Cur_intersection
     ;  Intersection = [X | Cur_intersection]).

在序言中查找两个列表之间没有重复项的交集

Finding intersection between two lists without duplicates in prolog

prolog

intersection