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

Question

У меня проблемы с запуском этой программы Prolog, которая берет два списка и возвращает true, если все члены первого списка являются членами второго списка, и false в противном случае.

Примеры:

?- members([a, c], [a, b, c, d])
true
?- members([d, a, c, a], [a, b, c, d, e])
true
?- members([b, e], [a, b, c, d])
false
?- members([], [a, b, c, d])
true

Как мне это сделать?Любая помощь приветствуется.

Answer 1

Вы можете использовать maplist для такого рода проблем, так как он следует за стандартным рекурсивным обходом списка:

mem(L, X) :- memberchk(X, L).
subset(S, L) :- maplist(mem(L), S).

Результаты:

| ?- subset([a,c], [a,b,c,d]).

yes
| ?- subset([c,a], [a,b,c,d]).

yes
| ?- subset([e], [a,b,c,d]).

no
| ?- subset([], [a,b,c,d]).

yes
| ?- subset(S, [a,b,c,d]), S=[_|_].

S = [a] ? ;

S = [a,a] ? ;

S = [a,a,a] ? ;
...

Обратите внимание, что оригинальное определение проблемы делаетНе исключаю случая, когда подмножество может иметь повторяющиеся элементы из надмножества.Если вы хотите ограничить подмножества количеством элементов, меньшим или равным количеству надмножеств, вы можете использовать select/3:

subset([], _).
subset([X|Xs], L) :-
    select(X, L, L1),
    subset(Xs, L1).

Результаты:

| ?- subset([a,c], [a,b,c,d,e]).

true ? ;

no
| ?- subset([a,f], [a,b,c,d,e]).

no
| ?- subset([a,a], [a,b,c,d,e]).

no
| ?- subset(S, [a,b,c]), S=[_|_].

S = [a] ? ;

S = [a,b] ? ;

S = [a,b,c] ? ;

S = [a,c] ? ;

S = [a,c,b] ? ;

S = [b] ? ;

S = [b,a] ? ;
...

S = [c,b] ? ;

S = [c,b,a] ? ;

no

обратите внимание, что список [c,b,a] считается другим списком в Прологе по сравнению с [a,b,c], поэтому это отдельное решение.Если вы хотите, чтобы списки вели себя как наборы, это другое решение.

Answer 2

«Мы ничего не пробовали, и у нас нет идей»

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

$ swipl
?- subset([a, c], [a, b, c, d]).
true.

?- subset([d, a, c, a], [a, b, c, d, e]).
true.

?- subset([b, e], [a, b, c, d]).
false.

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

Этозадокументировано здесь: http://www.swi -prolog.org / pldoc / doc_for? object = subset / 2

Вы можете нажать на маленький желтый кружок с двоеточием и тире, чтобы увидеть, как онреализовано: http://www.swi -prolog.org / pldoc / doc / SWI / library / lists.pl? show = src # subset / 2

713 subset([], _) :- !.
714 subset([E|R], Set) :-
715     memberchk(E, Set),
716     subset(R, Set).

Это определение примерно такое же, как:

maplist([M]>>memberchk(M, Set), Subset)

Это определение всегда успешно или терпит неудачу только один раз.Это по замыслу.

Это также может быть реализовано так:

maplist([M]>>member(M, Set), Subset)

И это ведет себя как предложение в комментариях:

?- maplist([M]>>member(M, [a,b]), Subset).
Subset = [] ;
Subset = [a] ;
Subset = [a, a] ;
Subset = [a, a, a] ;
Subset = [a, a, a, a] .

?- length(Subset, _), maplist([M]>>member(M, [a,b]), Subset).
Subset = [] ;
Subset = [a] ;
Subset = [b] ;
Subset = [a, a] ;
Subset = [a, b] ;
Subset = [b, a] ;
Subset = [b, b] ;
Subset = [a, a, a] ;
Subset = [a, a, b] .