PROLOG: определение того, являются ли элементы в списке равными, если порядок не имеет значения

Ответ 1

Простое решение с использованием встроенного предиката 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

Ответ 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, но тем самым мы потеряем logical-purity! Можем ли мы лучше?

Мы можем! Вводя 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, из-за размера набора решений бесконечно (для всех, кроме самых тривиальных экземпляров, представляющих интерес).

Ответ 3

В Prolog вы часто можете делать именно то, что вы говорите

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

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

При необходимости переименуйте.

Ответ 4

компактная форма:

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

но использование члена /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).

Ответ 5

Другие ответы элегантны (намного выше моего собственного уровня Prolog), но мне показалось, что вопрос о нем

эффективен для регулярного использования.

Принятый ответ - O (max (| A | log (| A |), | B | log (| B |)), независимо от того, равны ли списки (до перестановки) или нет.

По крайней мере, он должен был заплатить, чтобы проверить длины, прежде чем беспокоиться о сортировке, что уменьшит время выполнения до чего-то линейного по длине списков в случае, когда они не имеют одинаковой длины.

Расширяя это, нетрудно изменить решение, чтобы его время выполнения было фактически линейным в общем случае, когда списки не равны (вплоть до перестановки), используя случайный переваривает.

Предположим, что мы определим

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

Это версия Пролога математической функции 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.

Если два списка имеют разные дайджесты, они не могут быть равными. Если в двух списках есть один и тот же дайджест, то есть крошечный шанс, что они неравны, но это еще нужно проверить. В этом случае я бесстыдно украл Пауло Мууру отличный ответ.

Последний код:

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

Ответ 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).