長度有序的子集？

Question

我試圖做一個代碼，以的順序生成集合的所有子集。 也就是說，調用subset([1,2,3], X)應該產生

X = []; 
X = [1]; 
X = [2]; 
X = [3]; 
X = [1,2]; 
X = [1,3]; 
X = [2,3]; 
X = [1,2,3]. 

內部順序並不那麼重要，只有最小的子集列第一（即我不在乎[2,3] [1日前來，2]，只有1，[2]和[3]在[2,3]之前）。

-

到目前爲止，我已經嘗試了兩種方法。首先，我試着自己做出這個謂詞......

subset([], []). 
subset(List, []). 
subset(List, [N]) :- 
    member(N, List). 

subset(List, [N|Rest]) :- 
    !, 
    nth0(I, List, N), 
    findall(E, (nth0(J, List, E), J > I), NewList), 
    subset2(NewList, Rest). 

......但它甚至沒有達到預期的效果。其次，我嘗試製作powerset（使用this subset predicate）並使用list_to_ord_set/2進行排序，但是我也無法使其工作。

幫助？

Answer 1

我發現一個不那麼完美的解決方案......它需要切割和一些內建

subset(Xs, Ys) :- 
    length(Xs, L), 
    between(0, L, N), 
    length(Ys, N), 
    assign(Xs, Ys). 

assign(_, []) :- !. 
assign([X|Xs], [X|Ys]) :- 
    assign(Xs, Ys). 
assign([_|Xs], Ys) :- 
    assign(Xs, Ys). 

由@Fatalize指出的那樣，我們能夠避免晉級，只是迫使在第一個參數的空列表1 ^子句：

assign([], []). 
assign([X|Xs], [X|Ys]) :- 
    assign(Xs, Ys). 
assign([_|Xs], Ys) :- 
    assign(Xs, Ys). 

我回避掉2^3 ^條款，從而「自然」訂單仍然保持很好

Answer 2

也總是考慮使用DCG notation磨片n描述列表。

例如：

list_sublist(Ls0, Ls) :- 
     same_length(Ls0, Ls1), 
     append(Ls, _, Ls1), 
     phrase(sublist(Ls0), Ls). 

sublist([])  --> []. 
sublist([L|Ls]) --> ([] ; [L]), sublist(Ls). 

樣品查詢：

?- list_sublist([a,b,c], Ls). 
Ls = [] ; 
Ls = [c] ; 
Ls = [b] ; 
Ls = [a] ; 
Ls = [b, c] ; 
Ls = [a, c] ; 
Ls = [a, b] ; 
Ls = [a, b, c] ; 
false. 

又如：

?- list_sublist(Ls, [b,c]). 
Ls = [b, c] ; 
Ls = [_G511, b, c] ; 
Ls = [b, _G514, c] ; 
Ls = [b, c, _G517] ; 
etc. 

最常見的情況：

?- list_sublist(Xs, Ys). 
Xs = Ys, Ys = [] ; 
Xs = [_G513], 
Ys = [] ; 
Xs = Ys, Ys = [_G513] 
Xs = [_G513, _G516], 
Ys = [] ; 
etc.