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

在哪里我会尝试重建左边的那个以及最后的交换列表; 但这次失败了.

我对递归的感觉非常差,根本不知道如何改进它,尤其是Prolog.任何提示或建议都将在此时受到赞赏.

Answer 1

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

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 2

作为起点,让我们equal_elements/2来看看@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,但通过这样做,我们将失去逻辑纯度!我们可以做得更好吗？

我们可以! 引入selectd/3一个逻辑上纯粹的谓词,结合了确定性selectchk/3和纯度select/3.selectd/3基于 if_/3和(=)/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.

受@AmiTavory给出的答案的启发,我们可以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

请注意,相同的"技巧"不起作用equal_elementsC/2,因为解决方案集的大小是无限的(除了最感兴趣的所有实例).

Answer 3

在Prolog中,您经常可以完全按照您的意思行事

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

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

必要时重命名.

Answer 4

紧凑的形式:

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

但是,使用member/2似乎效率低下,并且留下空间来模糊重复(两边).相反,我会使用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).