На самом деле на самом деле зависит от того, как будет использоваться предикат.
Предполагая, что «множество» действительно является списком Пролога без дубликатов, но не в каком-либо конкретном порядке; тогда два набора в этом представлении «совпадают», если они являются перестановками друг друга. Другими словами, было бы достаточно определить eq_set/2 как:
eq_set(A, B) :-
my_permutation(A, B).
и просто используйте определение учебника permutation/2, в котором используется определение учебника select/3 (см. «Искусство пролога (второе издание)» Стерлинга и Шапиро, стр. 67-9):
my_permutation([], []).
my_permutation(Xs, [Y|Ys]) :-
my_select(Y, Xs, Xs0),
my_permutation(Xs0, Ys).
my_select(X, [X|Xs], Xs).
my_select(X, [Y|Ys], [Y|Zs]) :-
my_select(X, Ys, Zs).
(Я переименовал их только для того, чтобы убедиться, что я не использую определения стандартной библиотеки; в SWI-Prolog есть и select/3, и permutation/2 в автозагрузке библиотека (списки) ; определения в основном те же, но они выполняют некоторую проверку типов во время выполнения для аргументов.)
Вот как вы можете его использовать:
?- eq_set([1,2,3], [2,3,1]).
true ;
false.
?- eq_set([1,2,3], S).
S = [1, 2, 3] ;
S = [1, 3, 2] ;
S = [2, 1, 3] ;
S = [2, 3, 1] ;
S = [3, 1, 2] ;
S = [3, 2, 1] ;
false.
?- eq_set([1,2,3], [1,2]).
false.
?- eq_set(A, B).
A = B, B = [] ;
A = B, B = [_4480] ;
A = B, B = [_4480, _4492] ;
...
Я не уверен, насколько полезен последний запрос. Вы можете заставить его перечислять решения в порядке увеличения размера «множества», например:
?- length(S1, _), eq_set(S1, S2), numbervars(S1).
S1 = S2, S2 = [] ;
S1 = S2, S2 = [A] ;
S1 = S2, S2 = [A, B] ;
S1 = [A, B],
S2 = [B, A] ;
S1 = S2, S2 = [A, B, C] ;
S1 = [A, B, C],
S2 = [A, C, B] ;
S1 = [A, B, C],
S2 = [B, A, C] ;
S1 = [A, B, C],
S2 = [B, C, A] ;
S1 = [A, B, C],
S2 = [C, A, B] ;
S1 = [A, B, C],
S2 = [C, B, A] ;
S1 = S2, S2 = [A, B, C, D] .
(Не беспокойтесь о numbervars, он просто дает читаемые имена всем свободным переменным в наборах. Имейте в виду, что объединение двух свободных переменных делает их одной и той же переменной.)
Это отправная точка, но, возможно, она уже достаточно хороша. Самым вопиющим упущением является то, что аргументы не должны быть списками без дубликатов. Один из способов определить это - потребовать, чтобы каждый элемент отличался от всех других элементов. Поскольку слово «отличается» является коммутативным, вы можете определить его следующим образом:
is_set([]).
is_set([X|Xs]) :-
all_different(Xs, X),
is_set(Xs).
all_different([], _).
all_different([Y|Ys], X) :-
dif(X, Y),
all_different(Ys, X).
Используется dif/2, который является широко доступным предикатом (но есть ли у вашего Пролога?).
Возможно, мы использовали бы maplist для последнего:
is_set([]).
is_set([X|Xs]) :-
maplist(dif(X), Xs).
is_set(Xs).