Prolog程序：查找两个列表的任意顺序相等

Question

我想编写一个Prolog程序来查找两个列表的相等性，其中元素的顺序不重要。因此我编写了以下代码：

del(_, [], []) .
del(X, [X|T], T).  
del(X, [H|T], [H|T1]) :-
   X \= H,
   del(X, T, T1).

member(X, [X|_]).  
member(X, [_|T]) :- 
   member(X, T).

equal([], []).  
equal([X], [X]).  
equal([H1|T], L2) :-
   member(H1, L2),
   del(H1, L2, L3),
   equal(T, L3).  

但是当我输入equal([1,2,3],X).时，它并没有显示出所有可能的X值。相反，程序在中间卡住了。可能的原因是什么？

- Happy Mittal

---

确定两个集合的相等性 - Numid

Answer 1

isSubset([],_).
isSubset([H|T],Y):-
    member(H,Y),
    select(H,Y,Z),
    isSubset(T,Z).
equal(X,Y):-
    isSubset(X,Y),
    isSubset(Y,X).

- Mr. Berna

---

在 select/3 之前的 member/2 是不必要的。equal/2 不起作用：它只给出一个解决方案，然后在重做时挂起：?- equal([1,2,3],X)。X = [1, 2, 3]；错误：由于内存不足而中止执行。因此，对答案进行投票否定。 - user502187

Answer 2

尝试使用谓词检查两个集合中是否存在一个是另一个的排列组合：

delete(X, [X|T], T).

delete(X, [H|T], [H|S]):-
    delete(X, T, S).


permutation([], []).

permutation([H|T], R):-
    permutation(T, X), delete(H, R, X).

(该谓词源自http://www.dreamincode.net/code/snippet3411.htm)

请提供需要翻译的具体内容。

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

- ULazdins

---

链接已失效。 - Mateusz Piotrowski

Answer 3

您所观察到的不终止的实际原因是：以下子句并未以任何方式约束L2。因此，您的查询?- equal([1,2,3], X).意味着证明目标member(_, L2)，该目标在普遍情况下无法终止。因此，equal([1,2,3], X)也无法普遍终止！有关如何解释Prolog代码的非终止信息，请阅读failure-slice的更多信息！

---

PS. 从一个不同的角度来看终止问题，我们可以看到在这种情况下非终止实际上是必然的结果。

为什么？因为你没有限制重复的数量，这使得解集的大小无限。该集合不能由有限数量的答案表示（前提是您不允许延迟目标）。

- repeat

Answer 4

如果你不关心列表元素的重复性， 可以使用ground/1检查是否已经实例化， 并使用iwhen/2进行强制实例化， 然后通过sort/2消除重复项，如下所示：

same_elements(As, Bs) :-
   iwhen(ground(As+Bs), (sort(As,Es),sort(Bs,Es))).

使用 SWI Prolog 8.0.0 的示例：

?- same_elements([a,c,c,b,a,c], [c,b,b,a]).
true.
?- same_elements([a,b,b,a], [b,a,b,e]).
false.
?- same_elements([a,b,b,a], Xs).
错误：参数未充分实例化

- repeat

Answer 5

怎么样：

equal(X, Y) :-
    subtract(X, Y, []),
    subtract(Y, X, []).

- DrBeco

Answer 6

试试这个：

equal([],[]).
equal([Ha|Ta],[Hb|Tb]) :-
   Ha = Hb, lequal(Ta,Tb).

- user357823

Answer 7

那么为什么你的代码中的equal([1,2,3], X)不能普遍终止呢？

让我们来看看你的代码的失败片段！什么是失败片段？以下是标签信息：

失败片段是通过添加一些目标false而获得的Prolog程序片段。失败片段有助于定位纯单调Prolog程序普遍非终止的原因。它们还有助于给出所需推理次数的下限。这是一种具体的程序切片技术。

要创建一个失败片段：

• 我们将false目标插入程序中
• 同时确保该片段不会以上述目标终止。

del(_, [], []) :- false.
del(X, [X|T], T) :- false.
del(X, [H|T], [H|T1]) :-
   dif(X, H),
   del(X, T, T1).
member(X, [X|_]).  
member(X, [_|T]) :- 
   member(X, T).
equal([], []) :- false.
equal([X], [X]) :- false.
equal([H1|T], L2) :-
   member(H1, L2),
   del(H1, L2, L3),
   equal(T, L3).
?- equal([1,2,3], _), false.
** LOOPS **

以上的失败分析告诉我们什么呢？它告诉我们：

• 为了使目标equal([1,2,3], X)普遍终止...
• ...我们必须改变至少一个剩余的部分（没有被划掉的）！

- repeat

Answer 8

简要地说

equal([],[]).
equal([H|T],[H|T1]):-equal(T,T1).

- dodushkaxy

---

如果列表中包含相同的项目但顺序不同，则此方法将无法正常工作。 - repeat

Answer 9

我建议使用内置的谓词msort/2，然后比较列表。在SWI Prolog上，它的时间复杂度为O(nlogn)，而通过逐个元素天真地检查未排序列表的时间复杂度为O(n²)。

lists_equal(List1, List2) :-
    msort(List1, Sorted1),
    msort(List2, Sorted2),
    Sorted1=Sorted2.

在这里，对列表进行排序需要O(nlogn)的时间，而在SWI Prolog上进行比较则需要O(n)的时间，我不清楚其他实现方式。

- Mehmet Emre