PROLOG：如果顺序无关紧要，则确定列表中的元素是否相等

Question

我正在尝试找出一种方法来检查两个列表是否相等，而不管它们的元素顺序如何。

我的第一次尝试是：

areq([],[]).
areq([],[_|_]).
areq([H1|T1], L):- member(H1, L), areq(T1, L).

然而，这只检查左边列表的所有元素是否存在于右边列表中；意思是 areq([1,2,3],[1,2,3,4]) => true。在这一点上，我需要找到一种能够在双向意义上测试事物的方法。我的第二次尝试如下：

areq([],[]).
areq([],[_|_]).
areq([H1|T1], L):- member(H1, L), areq(T1, L), append([H1], T1, U), areq(U, L).

我会在哪里尝试重建左边的 les，最后交换列表；但这惨遭失败。

我的递归意识极差，根本不知道如何改进，尤其是Prolog。任何提示或建议将不胜感激。

Answer 1

在 Prolog 中，您通常可以完全按照您说的去做

areq([],_).
areq([H1|T1], L):- member(H1, L), areq(T1, L).

bi_areq(L1, L2) :- areq(L1, L2), areq(L2, L1).

必要时重命名。

Answer 2

使用 sort/2 ISO 标准内置谓词的简单解决方案，假设两个列表都不包含重复元素：

equal_elements(List1, List2) :-
    sort(List1, Sorted1),
    sort(List2, Sorted2),
    Sorted1 == Sorted2.

一些示例查询：

| ?- equal_elements([1,2,3],[1,2,3,4]).
no

| ?- equal_elements([1,2,3],[3,1,2]).    
yes

| ?- equal_elements([a(X),a(Y),a(Z)],[a(1),a(2),a(3)]).
no

| ?- equal_elements([a(X),a(Y),a(Z)],[a(Z),a(X),a(Y)]).
yes

Answer 3

紧凑型：

member_(Ys, X) :- member(X, Ys).
equal_elements(Xs, Xs) :- maplist(member_(Ys), Xs).

但是，使用 member/2 似乎效率低下，并留下 space 对重复（双方）的歧义。相反，我会使用 select/3

?- [user].

equal_elements([], []).
equal_elements([X|Xs], Ys) :-
  select(X, Ys, Zs),
  equal_elements(Xs, Zs).

^D 这里

1 ?- equal_elements(X, [1,2,3]).
X = [1, 2, 3] ;
X = [1, 3, 2] ;
X = [2, 1, 3] ;
X = [2, 3, 1] ;
X = [3, 1, 2] ;
X = [3, 2, 1] ;
false.

2 ?- equal_elements([1,2,3,3], [1,2,3]).
false.

或者更好，

equal_elements(Xs, Ys) :- permutation(Xs, Ys).

Answer 4

作为起点，让我们来看看@CapelliC 的第二个实现：

equal_elements([], []).
equal_elements([X|Xs], Ys) :-
   select(X, Ys, Zs),
   equal_elements(Xs, Zs).

上面的实现为这样的查询留下了无用的选择点：

?- equal_elements([1,2,3],[3,2,1]).
true ;                                 % succeeds, but leaves choicepoint
false.

我们能做什么？我们可以通过使用解决效率问题 selectchk/3 而不是 select/3, but by doing so we would lose logical-purity！ 我们可以做得更好吗？

我们可以！ 引入 selectd/3，一个逻辑上纯的谓词，结合了 selectchk/3 的确定性和 select/3 的纯度。 selectd/3 基于 if_/3 and (=)/3:

selectd(E,[A|As],Bs1) :-
    if_(A = E, As = Bs1, 
               (Bs1 = [A|Bs], selectd(E,As,Bs))).

selectd/3 可以直接替代 select/3，所以使用起来很简单！

equal_elementsB([], []).
equal_elementsB([X|Xs], Ys) :-
   selectd(X, Ys, Zs),
   equal_elementsB(Xs, Zs).

让我们看看实际效果！

?- equal_elementsB([1,2,3],[3,2,1]).
true.                                  % succeeds deterministically

?- equal_elementsB([1,2,3],[A,B,C]), C=3,B=2,A=1.
A = 1, B = 2, C = 3 ;                  % still logically pure
false.

编辑 2015-05-14

OP 没有具体说明谓词应该强制项目出现在双方相同的多重性。 equal_elementsB/2 是这样做的，如以下两个查询所示：

?- equal_elementsB([1,2,3,2,3],[3,3,2,1,2]).
true.
?- equal_elementsB([1,2,3,2,3],[3,3,2,1,2,3]).
false.

如果我们希望第二个查询成功，我们可以通过使用元谓词以逻辑上纯的方式放宽定义 tfilter/3 和具体化的不平等 dif/3:

equal_elementsC([],[]).
equal_elementsC([X|Xs],Ys2) :-
   selectd(X,Ys2,Ys1),
   tfilter(dif(X),Ys1,Ys0),
   tfilter(dif(X),Xs ,Xs0),
   equal_elementsC(Xs0,Ys0).

让我们运行像上面那样进行两个查询，这次使用 equal_elementsC/2:

?- equal_elementsC([1,2,3,2,3],[3,3,2,1,2]).
true.
?- equal_elementsC([1,2,3,2,3],[3,3,2,1,2,3]).
true.

编辑 2015-05-17

实际上，equal_elementsB/2 在以下情况下不会普遍终止：

?- equal_elementsB([],Xs), false.         % terminates universally
false.    
?- equal_elementsB([_],Xs), false.        % gives a single answer, but ...
%%% wait forever                          % ... does not terminate universally

但是，如果我们翻转第一个和第二个参数，我们就会终止！

?- equal_elementsB(Xs,[]), false.         % terminates universally
false.
?- equal_elementsB(Xs,[_]), false.        % terminates universally
false.

受到的启发，我们可以通过"sharpening"这样的解决方案集来改进equal_elementsB/2的实现：

equal_elementsBB(Xs,Ys) :-
   same_length(Xs,Ys),
   equal_elementsB(Xs,Ys).

为了检查非终止是否消失，我们使用两个谓词进行查询：

?- equal_elementsB([_],Xs), false.
%%% wait forever                          % does not terminate universally

?- equal_elementsBB([_],Xs), false.
false.                                    % terminates universally

请注意，相同的 "trick" 不适用于 equal_elementsC/2，因为解决方案集的大小是无限的（除了感兴趣的最琐碎的实例之外的所有实例）。

Answer 5

其他答案都很优雅（远高于我自己的 Prolog 水平），但让我印象深刻的是问题的陈述

efficient for the regular uses.

接受的答案是 O(max(|A| log(|A|), |B|log(|B|)), 无关列表是否相等（最多排列）。

至少，在麻烦排序之前检查长度是值得的，这会在列表长度不相等的情况下将运行时间减少到与列表长度成线性的程度。

扩展这个，不难修改解决方案，使其运行时间在列表不相等（最多排列）的一般情况下有效线性，使用随机 digests.

假设我们定义

digest(L, D) :- digest(L, 1, D).
digest([], D, D) :- !.
digest([H|T], Acc, D) :-
    term_hash(H, TH),
    NewAcc is mod(Acc * TH, 1610612741),
    digest(T, NewAcc, D).

这是数学函数的 Prolog 版本 Prod_i h(a_i) | p，其中 h 是散列，p 是素数。它有效地将每个列表映射到 0, ...., p - 1 范围内的随机（在哈希意义上）值（在上面，p是大质数1610612741).

我们现在可以检查两个列表是否具有相同的摘要：

same_digests(A, B) :-
    digest(A, DA),
    digest(B, DB),
    DA =:= DB.

如果两个列表的摘要不同，则它们不能相等。如果两个列表具有相同的摘要，那么它们不相等的可能性很小，但这仍然需要检查。对于这种情况，我无耻地窃取了 Paulo Moura 的出色答案。

最终代码是这样的：

equal_elements(A, B) :-
    same_digests(A, B),
    sort(A, SortedA),
    sort(B, SortedB),
    SortedA == SortedB.

same_digests(A, B) :-
    digest(A, DA),
    digest(B, DB),
    DA =:= DB.

digest(L, D) :- digest(L, 1, D).
digest([], D, D) :- !.
digest([H|T], Acc, D) :-
    term_hash(H, TH),
    NewAcc is mod(Acc * TH, 1610612741),
    digest(T, NewAcc, D).

Answer 6

一种可能，灵感来自qsort：

split(_,[],[],[],[]) :- !.
split(X,[H|Q],S,E,G) :-
    compare(R,X,H),
    split(R,X,[H|Q],S,E,G).

split(<,X,[H|Q],[H|S],E,G) :-
    split(X,Q,S,E,G).
split(=,X,[X|Q],S,[X|E],G) :-
    split(X,Q,S,E,G).
split(>,X,[H|Q],S,E,[H|G]) :-
    split(X,Q,S,E,G).


cmp([],[]).
cmp([H|Q],L2) :-
    split(H,Q,S1,E1,G1),
    split(H,L2,S2,[H|E1],G2),
    cmp(S1,S2),
    cmp(G1,G2).

Answer 7

使用 cut 的简单解决方案。

areq(A,A):-!.
areq([A|B],[C|D]):-areq(A,C,D,E),areq(B,E).
areq(A,A,B,B):-!.
areq(A,B,[C|D],[B|E]):-areq(A,C,D,E).

一些示例查询：

?- areq([],[]).
true.

?- areq([1],[]).
false.

?- areq([],[1]).
false.

?- areq([1,2,3],[3,2,1]).
true.

?- areq([1,1,2,2],[2,1,2,1]).
true.

PROLOG：如果顺序无关紧要，则确定列表中的元素是否相等

PROLOG: Determining if elements in list are equal if order does not matter

prolog

编辑 2015-05-14

编辑 2015-05-17