Prolog中没有重复元素的两个列表的交集

Question

我需要编写一个程序来查找两个列表的交集。我不能使用剪切，结果列表中不应有任何重复元素。

这是我的代码：

intersection([],_,[]).
intersection([X|Xs],Y,[X|Zs]) :-
    member(X,Y),
    intersection(Xs,Y,Zs).
intersection([_|Xs],Y,Zs) :-
    intersection(Xs,Y,Zs).

当我运行以下查询时，我得到这些答案：

?- intersection([a,b,c,a],[a,v,c],L).
L = [a, c, a] ;
L = [a, c] ;            % <---------- this is only answer I want to get
L = [a, a] ;
L = [a] ;
L = [c, a] ;
L = [c] ;
L = [a] ;
L = [].

我能做什么？我只想得到 L = [a,c]，没有别的...你能帮忙吗？

Answer 1

如果 "conjunction" 你的意思是 "intersection"，你应该看看 SWI-Prolog library(lists) of the predicate intersection/3 中的实现。它包含削减，但如果你不介意所有的选择点，你可以省略它们。

有了它：

?- intersection([a,b,c,a],[a,v,c],I).
I = [a, c, a].

当然，这甚至在库谓词中也不起作用，因为您需要 sets 与您当前的定义。（如果只有第一个参数是一个集合就足够了。）

您可以使用 sort/2 谓词创建集合：如果第一个参数是一个有重复的列表，第二个参数将是一个没有重复的排序列表，例如：

?- sort([a,b,c,a], S1), intersection(S1, [a,v,c], I).
S1 = [a, b, c],
I = [a, c].

或者也许：

?- sort([a,b,c,a], S1), intersection(S1, [a,v,c,c,a,c], I).
S1 = [a, b, c],
I = [a, c].

?- sort([a,b,c,a,b,c,a,b,c], S1), intersection(S1, [a,v,c,c,a,c], I).
S1 = [a, b, c],
I = [a, c].

如果对两个参数都进行排序，则可以使用 ord_intersection/3 from library(ordsets), implemented in terms of oset_int/3.

?- sort([a,b,c,a], S1), sort([a,v,c,c,a,c], S2), ord_intersection(S1, S2, I).
S1 = [a, b, c],
S2 = [a, c, v],
I = [a, c].

重要的是，oset_int/3 在其实现中没有使用任何削减。然而，它假定第一个和第二个参数是按 "standard order of terms" 排序的元素列表，并且没有重复项，如 sort/2.

所做的那样

如果出于某种原因您不想使用 sort/2，您可以使用累加器并在将元素带到交点之前对其进行检查：

my_intersection(Xs, Ys, Zs) :-
    my_intersection_1(Xs, Ys, [], Zs).
my_intersection_1([], _, Zs, Zs).
my_intersection_1([X|Xs], Ys, Zs0, Zs) :-
    member(X, Ys), \+ member(X, Zs0),
    my_intersection_1(Xs, Ys, [X|Zs0], Zs).
my_intersection_1([_|Xs], Ys, Zs0, Zs) :-
    my_intersection_1(Xs, Ys, Zs0, Zs).

当然，结果中元素的顺序现在将颠倒过来。如果这不是 "conjunction" 的意思，您可以将 my_intersection_1/4 的前两个子句重写为：

my_intersection_1([], _, _, []).
my_intersection_1([X|Xs], Ys, Zs0, [X|Zs]) :-
    member(X, Ys), \+ member(X, Zs0),
    my_intersection_1(Xs, Ys, [X|Zs0], Zs).

Answer 2

似乎像这样的事情是简单的方法：

intersection( Xs , Ys , Zs ) :-
  sort(Xs,X1)     , % order and de-dupe the 1st list so as to produce a set
  sort(Ys,Y1)     , % order and de-dupe the 2nd list so as to produce a set
  merge(Xs,Ys,Zs)   % merge the two [ordered] sets to produce the result
  .                 % easy!

merge( []     , []     , []     ) .
merge( []     , [_|_]  , []     ) .
merge( [_|_]  , []     , []     ) .
merge( [X|Xs] , [Y|Ys] , [X|Zs] ) :- X =  Y , merge(    Xs  ,    Ys  , Zs ) .
merge( [X|Xs] , [Y|Ys] , Zs     ) :- X <  Y , merge(    Xs  , [Y|Ys] , Zs ) .
merge( [X|Xs] , [Y|Ys] , Zs     ) :- X >  Y , merge( [X|Xs] ,    Ys  , Zs ) .

或者甚至只是这个[表现不佳]的一行代码：

intersection( Xs , Ys , Zs ) :- setof(Z,(member(Z,Xs),member(Z,Ys)),Zs).

Answer 3

在 my answer to the related question "Intersection and union of 2 lists" 中，我提出了逻辑纯谓词 list_list_intersectionSet/3。它应该符合你对 T 的要求！

这是 list_list_intersectionSet/3 的升级版，它基于：

单调条件 if_/3、
meta-predicate tfilter/3,
和具体化的测试谓词dif/3 and memberd_t/3。

我们开始：

list_list_intersectionSet([]     ,_ ,[]).
list_list_intersectionSet([A|As0],Bs,Cs0) :-
   if_(memberd_t(A,Bs), Cs0 = [A|Cs], Cs0 = Cs),
   tfilter(dif(A),As0,As), 
   list_list_intersectionSet(As,Bs,Cs).

让我们看看实际效果！

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

Answer 4

前面显示的限制交集的项目顺序：

?- list_list_intersectionSet([a,b],[a,b], [a,b]).
true.

?- list_list_intersectionSet([a,b],[a,b], [b,a]).
false.

在这个答案中，我们取消了该限制...保留 logical-purity 和确定性（对于基本情况）！

首先，我们使用 Prolog lambdas 定义 none_intersect/2 和 meta-predicate maplist/2.

none_intersect(As,Bs) 声明 As 中的所有成员不同于 Bs 中的所有成员。

:- use_module(library(lambda)).

none_intersect(As,Bs) :-
   maplist(\A^maplist(dif(A),Bs),As).

接下来，我们定义intersection_of_and/3---基于none_intersect/2（上面定义），meta-predicate tpartition/4 and reified term equality (=)/3:

intersection_of_and([],As,Bs) :-
   none_intersect(As,Bs).
intersection_of_and([X|Xs],As0,Bs0) :-
   tpartition(=(X),As0,[_|_],As),        % [_|_] = [X|_]
   tpartition(=(X),Bs0,[_|_],Bs),        % [_|_] = [X|_]
   intersection_of_and(Xs,As,Bs).

intersection_of_and(Xs,As,Bs) 表示

所有出现在 As 和 Bs 中的项目也出现在 Xs（第一个子句）中，
Xs 中的所有项目在 As 和 Bs 中至少出现一次（第二个子句），
并且列表 Xs 不包含任何重复项。

intersection_of_and/3 使用特定参数以启用第一个参数索引。

最后，我们定义 list_list_intersection/3，它具有 OP 使用的参数顺序：

list_list_intersection(As,Bs,Xs) :-
   intersection_of_and(Xs,As,Bs).

让我们运行一些疑问！首先，赏金提供者建议的查询：

?- list_list_intersection([a,b],[a,b], [b,a]).
true.

接下来，一个类似的查询，其中 3 个列表中的 3 个不同的项目具有 3 个不同的顺序：

?- list_list_intersection([a,b,c],[b,a,c], [c,a,b]).
true.

如果某些 x 只出现在 first/second 列表中怎么办？

?- list_list_intersection([a,b,c,x],[b,a,c], [c,a,b]).
true.

?- list_list_intersection([a,b,c],[b,a,c,x], [c,a,b]).
true.

如果某些项目在 first/second 列表中出现两次怎么办？

?- list_list_intersection([a,b,c],[b,a,c,b], [c,a,b]).
true.

?- list_list_intersection([a,b,c,c],[b,a,c], [c,a,b]).
true.

最后，如果交集包含重复项怎么办？交叉点不包含重复...

?- list_list_intersection([a,b,c],[b,a,c], [c,c,a,b]).
false.                                     % as expected

Answer 5

这可以用简单的集合论来解决：

    intersection(A,B,AnB):-
        subtract(A,B,AminusB),
        subtract(A,AminusB,K),
        sort(K,AnB).

查询：

   ?- intersection([a,b,c,a],[a,v,c],L).

输出是

    L = [a, c].

没有更多答案。

Prolog中没有重复元素的两个列表的交集

Intersection of two lists without duplicate elements in Prolog

list

prolog

duplicates