长度有序子集？

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^ 子句，所以 'natural' 顺序仍然很好地保留

Answer 2

在描述列表时也请始终考虑使用 DCG notation。

例如：

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.

长度有序子集？

Length ordered subsets?

list

prolog