list 2个列表的交集和并集

Intersection and union of 2 lists

提问by andreapier

i'm starting up learning prolog (i use SWI-prolog) and i did a simple exercise in which i have 2 lists and i want to calculate their intersection and union. Here is my code that works pretty well but i was asking myself if there is a better way to do it as i don't like to use the CUT operator.

我正在开始学习 prolog（我使用 SWI-prolog）并且我做了一个简单的练习，其中我有 2 个列表，我想计算它们的交集和并集。这是我的代码运行良好，但我问自己是否有更好的方法来做到这一点，因为我不喜欢使用CUT 运算符。

intersectionTR(_, [], []).
intersectionTR([], _, []).
intersectionTR([H1|T1], L2, [H1|L]):-
    member(H1, L2),
    intersectionTR(T1, L2, L), !.
intersectionTR([_|T1], L2, L):-
    intersectionTR(T1, L2, L).

intersection(L1, L2):-
    intersectionTR(L1, L2, L),
    write(L).


unionTR([], [], []).
unionTR([], [H2|T2], [H2|L]):-
    intersectionTR(T2, L, Res),
    Res = [],
    unionTR([], T2, L),
    !.
unionTR([], [_|T2], L):-
    unionTR([], T2, L),
    !.

unionTR([H1|T1], L2, L):-
    intersectionTR([H1], L, Res),
    Res \= [],
    unionTR(T1, L2, L).
unionTR([H1|T1], L2, [H1|L]):-
    unionTR(T1, L2, L).

union(L1, L2):-
    unionTR(L1, L2, L),
    write(L).

Keep in mind that i want to have just 1 result, not multiple results (even if correct) so running the code with this:

请记住，我只想得到 1 个结果，而不是多个结果（即使正确），因此使用以下代码运行代码：

?- intersect([1,3,5,2,4] ,[6,1,2]).

should exit with:

应该退出：

[1,2]
true.

and not with

而不是与

[1,2]
true ;
[1,2]
true ;
etc...

The same must be valid for union predicate.
As i said my code works pretty well but please suggest better ways to do it.
Thanks

对于联合谓词，同样必须有效。
正如我所说，我的代码运行良好，但请提出更好的方法。
谢谢

回答by magus

Also, not sure why you're dead against cuts, so long as their removal would not change the declaritive meaning of the code, as per your link. For example:

另外，不确定您为什么反对削减，只要根据您的链接，删除它们不会改变代码的声明性含义。例如：

inter([], _, []).

inter([H1|T1], L2, [H1|Res]) :-
    member(H1, L2),
    inter(T1, L2, Res).

inter([_|T1], L2, Res) :-
    inter(T1, L2, Res).

test(X):-
        inter([1,3,5,2,4], [6,1,2], X), !.

test(X).
X = [1, 2].

In the test bit where I call the code, I'm just saying do the intersection but I'm only interested in the first answer. There are no cuts in the predicate definitions themselves.

在我调用代码的测试位中，我只是说做交集，但我只对第一个答案感兴趣。谓词定义本身没有任何削减。

回答by repeat

The following is based on my previous answerto Remove duplicates in list (Prolog); the basic idea is, in turn, based on @false's answerto Prolog union for A U B U C.

以下内容基于我之前对Remove duplicates in list (Prolog) 的回答；其基本思想是，反过来，基于@虚假的答案，以Prolog的联盟AUBUC。

What message do I want to convey to you?

我想向你传达什么信息？

• You can describe what you want in Prolog with logical purity.
• Using if_/3and (=)/3a logically pure implementation can be
  • both efficient(leaving behind choice points only when needed)
  • and monotone(logically sound with regard to generalization / specialization).
• The implementation of @false's predicates if_/3and (=)/3doesuse meta-logical Prolog features internally, but (from the outside) behaves logically pure.

• 您可以在 Prolog 中以逻辑纯洁的方式描述您想要的内容。
• 使用if_/3和(=)/3逻辑上纯的实现可以是
  • 既高效（仅在需要时留下选择点）
  • 和单调（关于泛化/专业化在逻辑上是合理的）。
• @假的谓词的执行if_/3和(=)/3不使用的元逻辑Prolog的内部功能，但是（从外面）的行为逻辑纯。

The following implementation of list_list_intersection/3and list_list_union/3uses list_item_isMember/3and list_item_subtracted/3, defined in a previous answer:

以下实现list_list_intersection/3andlist_list_union/3使用list_item_isMember/3and list_item_subtracted/3，在之前的答案中定义：

list_list_union([],Bs,Bs).
list_list_union([A|As],Bs1,[A|Cs]) :-
    list_item_subtracted(Bs1,A,Bs),
    list_list_union(As,Bs,Cs).

list_list_intersection([],_,[]).
list_list_intersection([A|As],Bs,Cs1) :-
    if_(list_item_isMember(Bs,A), Cs1 = [A|Cs], Cs1 = Cs),
    list_list_intersection(As,Bs,Cs).

Here's the query you posted as part of your question:

这是您作为问题的一部分发布的查询：

?- list_list_intersection([1,3,5,2,4],[6,1,2],Intersection).
Intersection = [1, 2].                    % succeeds deterministically

Let's try something else... The following two queries should be logically equivalent:

让我们试试别的……下面的两个查询在逻辑上应该是等价的：

?- A=1,B=3, list_list_intersection([1,3,5,2,4],[A,B],Intersection).
A = 1,
B = 3,
Intersection = [1, 3].
?- list_list_intersection([1,3,5,2,4],[A,B],Intersection),A=1,B=3.
A = 1,
B = 3,
Intersection = [1, 3] ;
false.

And... the bottom line is?

而且……底线是？

• With pure code it's easy to stay on the side of logical soundness.
• Impure code, on the other hand, more often than not acts like "it does what it should" at first sight, but shows all kinds of illogical behaviour with queries like the ones shown above.

• 使用纯代码很容易保持逻辑健全性。
• 另一方面，不纯的代码往往乍一看就像“它做了它应该做的”，但通过上面显示的查询显示了各种不合逻辑的行为。

---

---

Edit 2015-04-23

编辑 2015-04-23

Neither list_list_union(As,Bs,Cs)nor list_list_intersection(As,Bs,Cs)guarantee that Csdoesn't contain duplicates. If that bothers you, the code needs to be adapted.

既不list_list_union(As,Bs,Cs)也不list_list_intersection(As,Bs,Cs)保证Cs不包含重复项。如果这让您感到困扰，则需要修改代码。

Here are some more queries (and answers) with Asand/or Bscontaining duplicates:

以下是更多带有As和/或Bs包含重复项的查询（和答案）：

?- list_list_intersection([1,3,5,7,1,3,5,7],[1,2,3,1,2,3],Cs).
Cs = [1, 3, 1, 3].
?- list_list_intersection([1,2,3],[1,1,1,1],Cs).
Cs = [1].

?- list_list_union([1,3,5,1,3,5],[1,2,3,1,2,3],Cs).
Cs = [1, 3, 5, 1, 3, 5, 2, 2]. 
?- list_list_union([1,2,3],[1,1,1,1],Cs).
Cs = [1, 2, 3].
?- list_list_union([1,1,1,1],[1,2,3],Cs).
Cs = [1, 1, 1, 1, 2, 3].

---

---

Edit 2015-04-24

编辑 2015-04-24

For the sake of completeness, here's how we could enforce that the intersection and the union are sets---that is lists that do not contain any duplicate elements.

为了完整起见，下面是我们如何强制交集和并集是集合——即不包含任何重复元素的列表。

The following code is pretty straight-forward:

以下代码非常简单：

list_list_intersectionSet([],_,[]).
list_list_intersectionSet([A|As1],Bs,Cs1) :-
    if_(list_item_isMember(Bs,A), Cs1 = [A|Cs], Cs1 = Cs),
    list_item_subtracted(As1,A,As),
    list_list_intersectionSet(As,Bs,Cs).

list_list_unionSet([],Bs1,Bs) :-
    list_setB(Bs1,Bs).
list_list_unionSet([A|As1],Bs1,[A|Cs]) :-
    list_item_subtracted(As1,A,As),
    list_item_subtracted(Bs1,A,Bs),
    list_list_unionSet(As,Bs,Cs).

Note that list_list_unionSet/3is based on list_setB/2, defined here.

注意，list_list_unionSet/3是基于list_setB/2，定义在这里。

Now let's see both list_list_intersectionSet/3and list_list_unionSet/3in action:

现在让我们看看两者list_list_intersectionSet/3并list_list_unionSet/3在行动：

?- list_list_unionSet([1,2,3,1,2,3,3,2,1],[4,5,6,2,7,7,7],Xs).
Xs = [1, 2, 3, 4, 5, 6, 7].

?- list_list_intersectionSet([1,2,3,1,2,3,3,2,1],[4,5,6,2,7,7,7],Xs).
Xs = [2].

---

---

Edit 2019-01-30

编辑 2019-01-30

Here is an additional query taken from @GuyCoder's comment (plus two variants of it):

这是从@GuyCoder 的评论中提取的附加查询（加上它的两个变体）：

?- list_list_unionSet(Xs,[],[a,b]).
   Xs = [a,b]
;  Xs = [a,b,b]
;  Xs = [a,b,b,b]
...

?- list_list_unionSet([],Xs,[a,b]).
   Xs = [a,b]
;  Xs = [a,b,b]
;  Xs = [a,b,b,b]
...

?- list_list_unionSet(Xs,Ys,[a,b]).
   Xs = [], Ys = [a,b]
;  Xs = [], Ys = [a,b,b]
;  Xs = [], Ys = [a,b,b,b]
...

With the old version of list_item_subtracted/3, above queries didn't terminate existentially.

使用旧版本的list_item_subtracted/3，上述查询不会以存在方式终止。

With the new one they do. As the solution set size is infinite, none of these queries terminate universally.

有了新的，他们做到了。由于解决方案集的大小是无限的，因此这些查询都不会普遍终止。

回答by magus

To cheat slightly less than my first answer, you could use the findallhigher order predicate which gets Prolog to do the recursion for you :

为了比我的第一个答案略少作弊，您可以使用findall高阶谓词，它让 Prolog 为您执行递归：

4 ?- L1=[1,3,5,2,4], L2=[6,1,2], findall(X, (nth0(N, L1, X), member(X, L2)), Res).
L1 = [1, 3, 5, 2, 4],
L2 = [6, 1, 2],
Res = [1, 2].

回答by magus

If the aim is to just 'get the job done', then swi prolog has built in primitives for exactly this purpose:

如果目标只是“完成工作”，那么 swi prolog 已经为此目的内置了原语：

[trace] 3 ?- intersection([1,3,5,2,4] ,[6,1,2], X).
intersection([1,3,5,2,4] ,[6,1,2], X).
X = [1, 2].

[trace] 4 ?- union([1,3,5,2,4] ,[6,1,2], X).
X = [3, 5, 4, 6, 1, 2].

回答by magus

And finally (really), you could use findall to find all the solutions, then use nth0 to extract the first one, which will give you the result you want without cuts, and keeps the predicates nice and clean, without have any additional predicates to trap/stop prolog doing what it does best - backtracking and finding multiple answers.

最后（真的），您可以使用 findall 找到所有解决方案，然后使用 nth0 提取第一个解决方案，这将为您提供您想要的结果而无需削减，并保持谓词干净整洁，无需任何额外的谓词陷阱/停止序言做它最擅长的事情 - 回溯并找到多个答案。

Edit: It's arguable that putting in extra predicates in the 'core logic' to prevent multiple results being generated, is as ugly/confusing as using the cuts that you are trying to avoid. But perhaps this is an academic exercise to prove that it can be done without using higher order predicates like findall, or the built-ins intersection/union.

编辑：在“核心逻辑”中加入额外的谓词以防止生成多个结果是有争议的，这与使用您试图避免的削减一样丑陋/令人困惑。但也许这是一个学术练习，以证明它可以在不使用 findall 等高阶谓词或内置交集/联合的情况下完成。

inter([], _, []).

inter([H1|T1], L2, [H1|Res]) :-
    member(H1, L2),
    inter(T1, L2, Res).

inter([_|T1], L2, Res) :-
    inter(T1, L2, Res).

test(First):-
        findall(Ans, inter([1,3,5,2,4], [6,1,2], Ans), Ansl), 
        nth0(0, Ansl, First).

回答by Saeid Zarrinmehr

I know this post is very old but I found a solution with minimum coding.

我知道这篇文章很旧，但我找到了一个编码最少的解决方案。

% intersection
intersection([],L1,L2,L3).
intersection([H|T],L2,L3,[H|L4]):-member(H,L2),intersection(T,L3,L3,L4).
% member
member(H,[H|T]).
member(X,[H|T]):-member(X,T).

To test the above code you should not enter L3. Here is an examples.

要测试上述代码，您不应输入 L3。这是一个例子。

?- intersection([w,4,g,0,v,45,6],[x,45,d,w,30,0],L).
L = [w, 0, 45].

回答by jlcdev

% Element X is in list?

% 元素 X 在列表中？

pert(X, [ X | _ ]).

pert(X, [ X | _ ])。

pert(X, [ _ | L ]):- pert(X, L).

pert(X, [ _ | L ]):- pert(X, L)。

% Union of two list

% 两个列表的并集

union([ ], L, L).

联合（[ ]，L，L）。

union([ X | L1 ], L2, [ X | L3 ]):- \+pert(X, L2), union(L1, L2, L3).

union([ X | L1 ], L2, [ X | L3 ]):- \+pert(X, L2), union(L1, L2, L3)。

union([ _ | L1 ], L2, L3):- union(L1, L2, L3).

union([ _ | L1 ], L2, L3):- union(L1, L2, L3)。

% Intersection of two list

% 两个列表的交集

inter([ ], _, [ ]).

间（[ ]，_，[ ]）。

inter([ X | L1 ], L2, [ X | L3 ]):- pert(X, L2), inter(L1, L2, L3).

inter([ X | L1 ], L2, [ X | L3 ]):- pert(X, L2), inter(L1, L2, L3)。

inter([ _ | L1 ], L2, L3):- inter(L1, L2, L3).

间（[ _ | L1 ]，L2，L3）：-间（L1，L2，L3）。