3

我是 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]).

返回所有结果，但最后它们只是挂起。有一个更好的方法吗？

4

2 回答 2

7

简短的回答：是的。

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

?-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目标，使得程序仍然不会终止，我们将有一个很好的线索来解决这个问题。例如：

相同元素（[]，[]）。
相同元素（[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。
错误的。

所以，我们已经删除了太多。下次尝试：

相同元素（[]，[]）。
相同元素（[H1|T1]，L2）：-
  我的长度（[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)。

这现在终止于“双向”。

于 2012-10-28T19:15:46.640 回答
0

尝试这个：

same(X, X).
same([A| B], [C| D]):-
    A=C,
    same(B,D).

如果它们相同，它将返回 true。否则为假。

于 2021-07-08T01:02:53.397 回答