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個子集。這就是這個解決方案所做的，但其他解決方案列舉了許多冗餘子集。