Я ищу предикат, который работает следующим образом:
?- subset([1,2,3], X).
X = [] ;
X = [1] ;
X = [2] ;
X = [3] ;
X = [1, 2] ;
X = [1, 2, 3] ;
X = [2, 3] ;
...
Я видел некоторые реализации subset, но все они работают, когда вы хотите проверить, является ли один список подмножеством другого, а не когда вы хотите сгенерировать подмножества. Любые идеи?
Здесь идет реализация:
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).
В 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.
Набор представляет собой набор объектов различных по определению. Процедура подмножества не должна заботиться о порядке элементов в наборе (в аргументах). Правильное решение (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.
Надеюсь, это поможет!
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