list - 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。相反，程序挂在中间。可能是什么原因？

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

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 

Answer 3

您观察到的未终止的实际原因是：以下子句不L2以任何方式、形状或形式进行限制。

等于（[H1|T]，L2）：-
   成员（H1，L2），
   德尔（H1，L2，L3），
   等于（T，L3）。

因此，您的查询?- equal([1,2,3], X).意味着证明member(_, L2)不会普遍终止的目标。因此equal([1,2,3], X)也不能普遍终止！

有关如何解释 Prolog 代码不终止的更多信息，请阅读failure-slice！

---

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

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

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])。
真的。

?- same_elements([a,b,b,a], [b,a,b,e])。
错误的。

?-same_elements([a,b,b,a], Xs)。
错误：参数没有充分实例化

Answer 5

试试这个：

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

Answer 6

怎么样：

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

Answer 7

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

让我们看一下您的代码的失败片段！什么是故障切片？这是标签信息：

故障片是通过添加一些目标获得的 Prolog 程序的片段false。失败切片有助于定位纯单调 Prolog 程序普遍不终止的原因。它们还有助于为所需的推理数量提供一个下限。它是一种具体的程序切片技术。

要创建故障切片：

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

德尔（_，[]，[]）：-假。
德尔（X，[X|T]，T）：-假。
del(X, [H|T], [H|T1]) :- false ,
    dif(X, H) , % 注意 OP 最初使用 `X \= H`
    del(X, T, T1)。

成员（X，[X|_]）。  
成员（X，[_|T]）：-
   成员（X，T）。

相等（[]，[]）：-假。
相等（[X]，[X]）：-假。
等于（[H1|T]，L2）：-
   成员（H1，L2），假，
   德尔（H1，L2，L3），
   等于（T，L3）。  

?- 等于（[1,2,3]，_），假。% 注意 `false` 是多余的 ...
 ** LOOPS **                       % ... 如上 `equal/2` 不能成功。

那么......上面的故障切片告诉我们什么？它说：

• 为了使目标equal([1,2,3], X)普遍终止......
• ...我们必须至少更改其余部分中的一个（未删除的部分）！

Answer 8

我建议使用内置 predicate 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) 时间，我不知道其他实现。

Answer 9

简要地

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