Подмножества в Prolog

Ответ 1

Здесь идет реализация:

subset([], []).
subset([E|Tail], [E|NTail]):-
  subset(Tail, NTail).
subset([_|Tail], NTail):-
  subset(Tail, NTail).

Он будет генерировать все подмножества, но не в порядке, указанном в вашем примере.

В соответствии с комментарием здесь идет объяснение:

Первое предложение является базовым. Он указывает, что пустой список является подмножеством пустого списка.

Вторая и третья статьи касаются рекурсии. Второе предложение гласит, что если два списка имеют одну и ту же Голова, а хвост правого списка - это подмножество хвоста левого списка, то правый список является подмножеством левого списка.

В третьем разделе говорится, что если мы пропустим главу левого списка, а правый список - подмножество хвоста левого списка, то правый список - это подмножество левого списка.

Процедура, показанная выше, генерирует упорядоченные множества. Для неупорядоченных наборов вы можете использовать permutation/3:

unordered_subset(Set, SubSet):-
  length(Set, LSet),
  between(0,LSet, LSubSet),
  length(NSubSet, LSubSet),
  permutation(SubSet, NSubSet),
  subset(Set, NSubSet).

Ответ 2

В http://www.probp.com/publib/listut.html вы найдете реализацию предиката с именем subseq0, который делает то, что вы хотите:

subseq0(List, List).
subseq0(List, Rest) :-
   subseq1(List, Rest).

subseq1([_|Tail], Rest) :-
   subseq0(Tail, Rest).
subseq1([Head|Tail], [Head|Rest]) :-
   subseq1(Tail, Rest).

Краткое объяснение: subseq0(X, Y) проверяет, является ли Y подмножеством подмножества, а subseq1(X, Y) проверяет, является ли Y правильным подмножеством s > подпоследовательность X.

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

?- subseq0([1,2,3], X).
X = [1, 2, 3] ;
X = [2, 3] ;
X = [3] ;
X = [] ;
X = [2] ;
X = [1, 3] ;
X = [1] ;
X = [1, 2] ;
false.

Ответ 3

Набор представляет собой набор объектов различных по определению. Процедура подмножества не должна заботиться о порядке элементов в наборе (в аргументах). Правильное решение (swi proog) может выглядеть так:

subset(_, []).
subset([X|L], [A|NTail]):-
    member(A,[X|L]),    
    subset(L, NTail),
    not(member(A, NTail)).

Для вопроса? - подмножества ([1,2,3], E) он будет генерировать:

E = [] ;
E = [1] ;
E = [1, 2] ;
E = [1, 2, 3] ;
E = [1, 3] ;
E = [2] ;
E = [2, 3] ;
E = [3] ;
E = [3, 2] ;
false.

Надеюсь, это поможет!

Ответ 4

append([],L,L).

append([H|T],L,[H|L1]):-append(T,L,L1).


subset([X|T],[X|L]) :-subset(T,L).

subset([X|T],[G|L]) :-subset([X],L),append(L2,[X|L3],[G|L]),append(L2,L3,L4),subset(T,L4).

subset([],_).

----------------------------------------------
?- subset([1,2],[1,2]).

yes

?- subset([1,2],[2,1]).

yes

?- subset([1,1],[1,2]).

no

?- subset(D,[1,2]).

D = [1,2] ;

D = [1] ;

D = [2,1] ;

D = [2] ;

D = '[]' ;

no