Перечислить ограничение неравенства

Я пытаюсь написать предикат Prolog (CLP), который построил бы ограничение, ограничивающее неравенство двух списков.

Более формально, имея два списка A=[A1,...,AN], B=[B1,...,BN], ограничение определяется как (A1 #\= B1) #\/ (A2 #\= B2) #\/ ... #\/ (AN #\= BN).

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

any_different([], []).
any_different([H1|T1], [H2|T2]):-
    H1 #\= H2 #\/ any_different(T1, T2).

Ответы

Ответ 1

Вам нужно создать дизъюнкцию и вернуть ее через третий аргумент:

any_different([], [], V) :-
    V #= 0.  % no differences between [] and []
any_different([H1|T1], [H2|T2], Disj) :-
    any_different(T1, T2, Disj0),
    Disj #<==> (H1 #\= H2) #\/ Disj0.

Теперь вызов any_different(List1, List2, AnyDiff) отображает переменную AnyDiff, которую вы можете передать в предикат маркировки вместе с вашими другими переменными. Указывая AnyDiff #= 0, вы можете ограничить List1 и List2 равными, а AnyDiff #= 1 приведет к их неравномерности.

Ответ 2

Я думаю, что, по крайней мере, в SWI-Prolog, предикат dif/2 и библиотека (clpfd) могли бы быть альтернативой reification:

?- L=[X,Y,Z], L ins 1..3, dif(L,[1,2,3]), label(L).
L = [1, 1, 1],
X = Y, Y = Z, Z = 1 ;
L = [1, 1, 2],
X = Y, Y = 1,
Z = 2 ;
...

Ответ 3

Здесь реализована реализация на основе sum/3 и clpfd reification (#<==>)/2:

not_equals_reified(X, Y, B) :-
    X #\= Y #<==> B.

any_different(Xs, Ys) :-
    maplist(not_equals_reified, Xs, Ys, Bs), 
    sum(Bs, #>, 0).

Используя meta-predicate maplist/4 нам даже не нужно писать рекурсивный код!