The length of ordered subsets?

Question

I am trying to create code that generates all subsets of a set in order . That is, a call to 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 is not so important, only the first smallest subsets are listed first (that is, I do not care that [2,3] precedes [1,2], only 1 , [2] and [3] to [2,3] )

-

I have tried two approaches so far. At first I tried to 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 is not even suitable for its intended purpose. Secondly, I tried to make poweret (using this subset predicate ) and sort using list_to_ord_set / 2, but I couldn’t get it working.

reference

Answer 1

I found a not-so-elegant solution ... it requires a cut and some built-in functions

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

as @Fatalize noted, we can avoid the cut by simply running the empty list in the first argument of the sentence 1 ^:

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

I avoided changing the positions of 2 ^ and 3 ^, so the "natural" order is still well preserved.

Answer 2

Always always use DCG notation when describing lists.

For instance:

 list_sublist(Ls0, Ls) :- same_length(Ls0, Ls1), append(Ls, _, Ls1), phrase(sublist(Ls0), Ls). sublist([]) --> []. sublist([L|Ls]) --> ( [] ; [L] ), sublist(Ls). 

Request example:

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

The most common case:

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