Prolog:检查两个列表是否具有相同的元素

Question

我是Prolog的新手,我在检查两个列表是否具有完全相同的元素时遇到了问题.元素可能具有不同的顺序.我有这个代码:

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

 same_elements([], []).
 same_elements([H1|T1], L2) :-      
    myremove(H1, L2, Nl2),  
    same_elements(T1, Nl2).

它的工作原理除外

?- same_elements([b,c,a], X).

返回第一个结果后导致内存不足错误.那么我试图通过检查列表的长度是否相等并检查H1是L2的成员来缩小结果集:

mylength([], 0).
mylength([_|T], R) :-
   mylength(T, Nr),
   R is Nr+1.

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

same_elements([], []).
same_elements([H1|T1], L2) :- 
   mylength([H1|T1], X),
   mylength(L2, Y),
   Y = X,
   mymember(H1, L2),
   myremove(H1, L2, Nl2),
   same_elements(T1, Nl2).

现在两个

?- same_elements([b,c,a], X).
?- same_elements(X, [b,c,a]). 

返回所有结果,但之后它们就会挂起.有一个更好的方法吗？

Answer 1

简短回答:是的.

但是,在进入这个问题之前,还有一个更有趣的问题:你是如何找到这些问题的？你一定很幸运能找到它们!我试过了:

?- same_elements([a,b,c,d,e,f,g],Xs).
Xs = [a, b, c, d, e, f, g] ;
Xs = [a, b, c, d, e, g, f] ;
Xs = [a, b, c, d, f, e, g] ;
Xs = [a, b, c, d, g, e, f] ;
...

...而且只是被所产生的解决方案所淹没.不,我没有耐心去解决所有问题.但是有一种更简单的方法来测试具体的查询:只需删除答案,只关注查询是否停止.为此,我添加了目标false:

?- same_elements([a,b,c,d,e,f,g],Xs), false.

现在,我们永远不会看到任何解决方案.但我们可能会观察到查询的终止.唉,这个查询现在可能循环.至少我们不再涉及不相关的解决方案.

为了进一步缩小未终止的原因,我们将false在您的计划中添加目标.该修改过的程序称为失败切片.通过这种方式,我们尝试缩小负责非终止的部分.如果我们成功地添加了false程序仍然没有终止的目标,我们将有一个很好的线索如何解决问题.例如:

same_elements([], []).
same_elements([H1|T1], L2) :-
  mylength([H1|T1], X), false,
  mylength(L2, Y),
  Y = X,
  mymember(H1, L2),
  myremove(H1, L2, Nl2),
  same_elements(T1, Nl2).

所以这几乎是你的程序,除了它有一个目标false.背后的目标false是通过明确表明它们是无关紧要的.

现在,查询终止:

?- same_elements([a,b,c,d,e,f,g],Xs), false.
false.

所以,我们已经删除了太多.接下来尝试:

same_elements([], []).
same_elements([H1|T1], L2) :-
  mylength([H1|T1], X),
  mylength(L2, Y), false,
  Y = X,
  mymember(H1, L2),
  myremove(H1, L2, Nl2),
  same_elements(T1, Nl2).

现在,查询没有终止!

这意味着:不要查看程序的其余部分.无论在那里写什么,都无法撤消这个循环!

所以我们现在可以思考可见部分:它既没有终止

?- same_elements([a,b,c,d,e,f,g],Xs).

也不是

?- same_elements(Xs,[a,b,c,d,e,f,g]).

罪魁祸首只是该计划的一小部分.

您的想法是确保两个列表的长度相同.

而不是使用长度谓词,定义一个新的:

list_same_length([], []).
list_same_length([_|Xs], [_|Ys]) :-
    list_same_length(Xs, Ys).

这现在终止于"双向".