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）,
   del(H1, L2, L3),
   equal(T, L3).

所以你的查询 ?- equal([1,2,3], X). 暗示证明目标 member(_, L2) 这不会普遍终止。所以 equal([1,2,3], X) 也无法普遍终止！

有关如何解释未终止序言代码的更多信息 失败板!

---

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

?- same_elements([a,b,b,a], [b,a,b,e]).
false.

?- 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. 。故障切片有助于本地化纯粹的单调序言计划的普遍不终止的原因。它们还有助于为所需的推论数提供一个下限。这是混凝土 程序切片 技术。

创建故障切片：

• 我们插入 错误的 目标进入计划
• 同时确保片段不会随上述目标终止。

del（_，[]，[]）： - 错误的.
del（x，[x | t]，t）： - 错误的.
del（x，[h | t]，[h | t1]）： - 错误的,
   dif（x，h）,                    % note that the OP originally used `X \= H`
   del（x，t，t1）.

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

平等的（[]， []） ：- 错误的.
等于（[x]，[x]）： - 错误的.
equal([H1|T], L2) :-
   member(H1, L2), 错误的,
   DEL（H1，L2，L3）,
   相等（t，l3）.  

?- equal([1,2,3], _), 错误的.     % note that `false` is redundant ...
**循环**                      % ... as above `equal/2` cannot succeed.

所以...上面的失败切片告诉我们什么？它说：

• 实现目标 equal([1,2,3], X) 普遍终止...
• ... 我们 必须改变 至少一个 其余部分 （不是 罢工)!

Answer 8

我建议使用内置谓词 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).