Программа Prolog, чтобы найти равенство двух списков в любом порядке

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 Каким-либо образом, форма или форма.

Равный ([H1 | T], L2): - член (H1, L2), дель (H1, L2, L3), равный (T, L3).

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

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

---

Придавать Глядя на проблему прекращения от другого угла, мы видим, что не расторжение, на самом деле, необходимые последствия в этом случае.

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

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]). истинный. - - Same_Elements ([a, b, b, a], [b, a, b, e]). ложный. ? - Same_elements ([a, b, b, a], xs).Ошибка: аргументы не являются достаточно созданными

Answer 5

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

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

Answer 6

Как насчет:

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

Answer 7

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

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

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

Чтобы создать ломтик отказа:

• Мы вставляем ложный Цели в программу
• Убедившись, что фрагмент не прекращается с вышеуказанной целью.

del (_, [], []): - ложный.
del (x, [x | t], t): - ложный.
del (x, [h | t], [h | t1]): - ложный,
   dif (x, h),% Обратите внимание, что OP изначально использовал `x  = h` del (x, t, t1)Отказ Член (X, [X | _]). Член (X, [_ | T]): - член (X, T).равный([], []) :- ложный.
равный ([x], [x]): - ложныйОтказ равный ([H1 | T], L2): - член (H1, L2), ложный,
   del (h1, l2, l3),
   равный (т, л3). Отказ ? - равный ([1,2,3], _), ложный. Отказ % Обратите внимание, что «ложь» является избыточным ...** петли ** % ... Как выше «равна / 2» не может добиться успеха.

Так что ... Что делает вышеупомянутый ломтик, скажи нам? Это говорит:

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

Answer 8

Я предлагаю использовать встроенный предикат msort/2, Затем сравнивая списки. Требуется O (NLOGN) Время на SWI Prolog, тогда как проверка неисправных списков наивно элемент-элемент примет O (n²) время.

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

Здесь сортировочные списки принимают время O (NLOGN), и сравнивая их принимает o (n) время на Swi Prolog, я не знаю о других реализациях.

Answer 9

Кратко

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