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

返回所有结果，但最后它们只是停滞在那里。有更好的方法吗？

- minus

---

你可以使用内置函数：same_elements(X,Y) :- msort(X,S),msort(Y,S)。 - CapelliC

我不知道为什么@false说我的答案是错误的建议。现在我已经删除了它。无论如何...你知道在Prolog中cut有什么用吗？ - CapelliC

当我尝试了你的建议 same_elements([b,c,a], X) 后，只返回了一个结果，但我想要全部。 - minus

@chac：请看我的答案：你建议更改可见部分之外的内容。因此，你的剪切将完全没有影响。 - false

@chac：请查看下面的失败片段。但是为了非常清楚：通过在myremove/3中添加一个切割，程序仍然像以前一样循环！ - false

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

罪魁祸首就是程序中的这个非常微小的部分。

你的想法是确保两个列表的长度相同。

但不要使用 length-predicate，而是定义一个新的函数：

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

现在这个函数可以"双向终止"了。

- false

---

谢谢！我之前不知道那个调试技巧，现在我的谓词终止了。 - minus

@CarolineM：你可能也想测试一次相同长度-然后使用你原来的定义，两个参数都是相同长度。 - false

Answer 2

试试这个：

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

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

- Hackerman

---

你可以使用 same([A| B], [A| D]) 来省略 A=C 的检查。但是，正如特别提到的那样，你的解决方案对于元素可能以不同的顺序出现的情况是行不通的。 - Mahmudul Haque