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

Question

Я новичок в Prolog. Я пытаюсь написать подмножество функций (Set, Subset), которое определяет, является ли Subset подмножеством Set (duh). Кроме того, если второй параметр не создается, он должен выводить все возможные подмножества. Прямо сейчас, он работает, когда оба параметра создаются, но когда я пытаюсь вывести все подмножества, он сталкивается с проблемой с элементом/2. Например:

?- subset([1,2,3], S). 
S = []; 
S = [1]; 
S = [1, 1]; 
S = [1, 1, 1]; 
... 

Вот мой код:

% subset/2 
% subset(Set, Subset) iff Subset is a subset of Set 
subset(_, []). 
subset(Set, [H|T]) :- 
    member(H, Set), 
    subset(Set, T). 

в основном, как мне сделать так, чтобы член не держать собирание первого варианта в комплекте? Заранее спасибо.

Answer 1

(Многие системы Prolog включая SICStus и SWI имеют в своей библиотеке в subset/2, а скорее subset(Subset, Set), и это также не является чистым отношением ...)

Все зависит от того, что вы имеете в виду с помощью набора. Действительно ли [1, 1] действительный набор? Они должны происходить в одном или другом порядке? Ваше определение в порядке, если вы допускаете дубликаты. Ведь ваше определение гласит:

set_subset(Set, Subset): Все элементы Subset элементы Set

То, что вы довольно удивлены, что у вас есть сейчас бесконечное множество решений. И, что еще хуже, этот набор перечисляется очень несправедливо. Если это только решения точного порядка перечислены, что вы беспокоитесь, считает:

?- length(Subset,N), set_subset([1,2,3], Subset). 
Subset = [], N = 0 ; 
Subset = [1], N = 1 ; 
Subset = [2], N = 1 ; 
Subset = [3], N = 1 ; 
Subset = [1, 1], N = 2 ; 
Subset = [1, 2], N = 2 ; 
Subset = [1, 3], N = 2 ; 
Subset = [2, 1], N = 2 ; 
Subset = [2, 2], N = 2 ; 
Subset = [2, 3], N = 2 ... 

Если вы хотите, чтобы Subset имеет конечное число решений, вы, вероятно, хотите, а подпоследовательность. См. this answer.

Answer 2

вместо члена/2, попробуйте выбрать/3

subset(_, []). 
subset(Set, [H|T]) :- 
    select(H, Set, Rest), 
    subset(Rest, T). 

так вы получите

?- subset([a,b,c],X). 
X = [] ; 
X = [a] ; 
X = [a, b] ; 
X = [a, b, c] ; 
X = [a, c] ; 
... 

Answer 3

Для перечисления подмножеств, я не думаю, что его необходимо также произвести перестановки, после того, как весь набор не должен заботиться о заказе. Таким образом, типичное text book решение:

% subset(-Subset, +Set) 
subset([X|L], [X|R]) :- 
    subset(L, R). 
subset(L, [_|R]) :- 
    subset(L, R). 
subset([], []). 

Сравните это с другими решениями:

Это решение:

?- subset(X, [1,2,3]), write(X), nl, fail; true. 
[1,2,3] 
[1,2] 
[1,3] 
[1] 
[2,3] 
[2] 
[3] 
[] 

остальные capellis решение:

?- subset([1,2,3], X), write(X), nl, fail; true. 
[] 
[1] 
[1,2] 
[1,2,3] 
[1,3] 
[1,3,2] 
[2] 
[2,1] 
[2,1,3] 
[2,3] 
[2,3,1] 
[3] 
[3,1] 
[3,1,2] 
[3,2] 
[3,2,1] 

Из теории множеств мы знаем | P (A) | = 2^| A |, поэтому для 3 элементов длинного ввода подмножество должно генерировать 8 подмножеств. Это то, что делает это решение, но другие решения перечисляют путь к множеству избыточных подмножеств.