Пролог программа для нахождения равенства двух списков в любом порядке

Question

Я хотел написать программу Пролог, чтобы найти равенство двух списков, где порядок элементов
не имеет значения Поэтому я написал следующее:

del(_, [], []) .
del(X, [X|T], T).  
del(X, [H|T], [H|T1]) :-
   X \= H,
   del(X, T, T1).

member(X, [X|_]).  
member(X, [_|T]) :- 
   member(X, T).

equal([], []).  
equal([X], [X]).  
equal([H1|T], L2) :-
   member(H1, L2),
   del(H1, L2, L3),
   equal(T, L3).  

Но когда я даю ввод типа equal([1,2,3],X)., он не показывает все возможные значения X. Вместо этого программа висит посередине. В чем может быть причина?

Answer 1

isSubset([],_).
isSubset([H|T],Y):-
    member(H,Y),
    select(H,Y,Z),
    isSubset(T,Z).
equal(X,Y):-
    isSubset(X,Y),
    isSubset(Y,X).

Answer 2

Попробуйте использовать предикат, который проверяет, является ли один из наборов перестановкой другого набора:

delete(X, [X|T], T).

delete(X, [H|T], [H|S]):-
    delete(X, T, S).


permutation([], []).

permutation([H|T], R):-
    permutation(T, X), delete(H, R, X).

(Предикат взят из http://www.dreamincode.net/code/snippet3411.htm)

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

Answer 3

Фактическая причина не прекращения, которое вы наблюдали, заключается в следующем: следующий пункт не ограничивает L2 каким-либо образом, формой или формой.

<b>equal([H1|T], L2) :- 
   member(H1, L2)</b>,
   del(H1, L2, L3),
   equal(T, L3).

Таким образом, ваш запрос ?- equal([1,2,3], X). подразумевает доказательство цели member(_, L2), которая не заканчивается универсально. Следовательно, equal([1,2,3], X) также не может завершаться универсально!

Для получения дополнительной информации о том, как объяснить отсутствие завершения кода Пролога, прочитайте о fail-slice !

---

PS. Глядя на проблему завершения с другой точки зрения, мы видим, что отсутствие завершения является, на самом деле, необходимым следствием в этом случае.

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

Answer 4

Если вас не волнует кратность элементов списка, проверить на достаточную реализацию с ground/1, применять его с iwhen/2, и удалите дубликаты с помощью sort/2 примерно так:

same_elements(As, Bs) :-
   iwhen(ground(As+Bs), (sort(As,Es),sort(Bs,Es))).

Пример использования с SWI Prolog 8.0.0:

?- same_elements([a,c,c,b,a,c], [c,b,b,a]).
true.

?- same_elements([a,b,b,a], [b,a,b,e]).
false.

?- same_elements([a,b,b,a], Xs).
<b>ERROR: Arguments are not sufficiently instantiated</b>

Answer 5

Так почему же equal([1,2,3], X) не заканчивается универсально с вашим кодом?

Давайте рассмотрим срез-ошибки вашего кода! Что такое ломтики сбоев? Вот информация тега:

Отказ-фрагмент - это фрагмент программы Prolog, полученный путем добавления некоторых целей false. Отказ-срезы помогают локализовать причины универсального не прекращения чисто монотонной программы Пролог. Они также помогают дать нижнюю границу для количества необходимых выводов. Это конкретная программа-нарезка техника.

Чтобы создать срез сбоя:

• вставляем <b>false</b> голов в программу
• , следя за тем, чтобы фрагмент не заканчивался с вышеуказанной целью.

<s>del(_, [], [])  :- <b>false</b></s>.
<s>del(X, [X|T], T) :- <b>false</b></s>.
<s>del(X, [H|T], [H|T1]) :- <b>false</b></s>,
   <s>dif(X, H)</s>,                    % note that the OP originally used `X \= H`
   <s>del(X, T, T1)</s>.

member(X, [X|_]).  
member(X, [_|T]) :- 
   member(X, T).

<s>equal([], []) :- <b>false</b></s>.
<s>equal([X], [X]) :- <b>false</b></s>.
equal([H1|T], L2) :-
   member(H1, L2), <b>false</b>,
   <s>del(H1, L2, L3)</s>,
   <s>equal(T, L3)</s>.  

?- equal([1,2,3], _), <b>false</b>.     % note that `false` is redundant ...
<i>** LOOPS **</i>                      % ... as above `equal/2` cannot succeed.

Итак ... что говорит нам вышеупомянутый срез? Там написано:

• Чтобы заставить цель equal([1,2,3], X) окончательно прекратить ...
• ... мы должны изменить хотя бы одну из оставшихся частей (те, которые не зачеркнуты )!

Answer 6

Как насчет:

equal(X, Y) :-
    subtract(X, Y, []),
    subtract(Y, X, []).

Answer 7

Попробуйте это:

equal([],[]).
equal([Ha|Ta],[Hb|Tb]) :-
   Ha = Hb, lequal(Ta,Tb).

Answer 8

Кратко

equal([],[]).
equal([H|T],[H|T1]):-equal(T,T1).

Answer 9

Я предлагаю использовать встроенный предикат msort/2, а затем сравнивать списки. Это занимает время O (nlogn) в прологе SWI, тогда как проверка несортированных списков наивно поэлементно занимает время O (n ² ).

lists_equal(List1, List2) :-
    msort(List1, Sorted1),
    msort(List2, Sorted2),
    Sorted1=Sorted2.

Здесь сортировка списков занимает O (nlogn) времени, а сравнение их занимает O (n) времени в Прологе SWI, я не знаю о других реализациях.