长度有序的子集？

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(使用此子集谓词)并使用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^ 子句，因此仍然很好地保留了“自然”顺序