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]，不需要其他的……你能帮忙吗？

- nofar mishraki

---

“conjunction” 的确切含义不太清楚。您是指 “intersection” 吗？ - user1812457

Answer 1

在我对相关问题“2个列表的交集和并集”的回答中，我提出了逻辑上纯粹的谓词list_list_intersectionSet/3。它应该完全符合您的要求！这是list_list_intersectionSet/3的一个改进版本，它基于：

• 单调条件 if_/3，
• 元谓语 tfilter/3，
• 以及反身测试谓词 dif/3 和 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].

- repeat

---

很高兴看到一个能够产生正确答案的解决方案。 - false

@repeat 有没有一种方法可以重写这个代码，避免使用 "dif" 和 "member_t"？我正在尝试只使用最简单的命令使其工作。 - Trixie the Cat

Answer 2

如果您所说的“conjunction”是指“交集”，那么您应该查看 SWI-Prolog library(lists) 中 intersection/3 谓词的实现。它包含剪枝，但如果您不介意所有选择点，可以将它们留下来。

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

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

您可以使用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].

如果您对两个参数进行排序，您可以使用library(ordsets)中基于oset_int/3实现的ord_intersection/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在其实现中不使用任何剪枝。但它假定第一个和第二个参数是按"标准术语顺序"排序且没有重复元素的元素列表，就像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).

当然，结果中元素的顺序现在将被反转。如果这不是你所说的“并集”，你可以例如重写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).

- user1812457

---

您的答案对于“未充分实例化的术语”是不正确的。 - false

@false 是的，对于“未充分实例化的术语”来说是不正确的。 - user1812457

当术语没有被充分实例化时，你如何期望初学者理解呢？ - false

Answer 3

之前展示的list_list_intersectionSet/3 限制了交集中的项目顺序：

？- list_list_intersectionSet([a,b],[a,b], [a,b]).
真。
？- list_list_intersectionSet([a,b],[a,b], [b,a]).
假。

在这个答案中，我们解除了这个限制...保留了逻辑纯度 和 确定性（对于地面情况）！

首先，我们使用Prolog lambdas和元谓词 maplist/2定义了none_intersect/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，元谓语 tpartition/4 和实例化术语相等性 (=)/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 使用特定的参数以启用第一个参数索引。

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

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

让我们运行一些查询！首先是悬赏者建议的查询：

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

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

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

如果一些元素只出现在第一个/第二个列表中会怎样？

？- list_list_intersection([a，b，c，x]，[b，a，c]，[c，a，b])。
真。
？- list_list_intersection([a，b，c]，[b，a，c，x]，[c，a，b])。
真。

如果某些项目在第一个/第二个列表中出现两次会怎样？

？- list_list_intersection([a，b，c]，[b，a，c，b]，[c，a，b])。
真。
？- list_list_intersection([a，b，c，c]，[b，a，c]，[c，a，b])。
真。

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

？- list_list_intersection([a，b，c]，[b，a，c]，[c，c，a，b])。
false。％预期的结果

- repeat

---

终止属性怎么样？ - false

@false。现在，我也想知道这个！将调查并编辑答案。希望cti能胜出:) - repeat

Answer 4

似乎像这样做会更容易：

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).

- Nicholas Carey

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].

没有更多的答案了。

- Vikram Venkat