Length ordered subsets?

Question

I'm trying to make a code that generates all subsets of a set in order. That is, calling subset([1,2,3], X) should generate

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

The internal order isn't all that important, only that the smallest subsets are listed first (i.e I don't care if [2,3] comes before [1,2], only that 1, [2] and [3] are before [2,3]).

--

I've tried two approaches thus far. First I tried making the predicate myself...

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).

...but it doesn't even come close to working as intended. Secondly I tried making the powerset (using this subset predicate) and ordering with list_to_ord_set/2, but I couldn't get it to work either.

Help?

Answer 1

Always also consider using DCG notation when describing lists.

For example:

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

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

Sample query:

?- 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.

Another example:

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

Most general case:

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