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?

score 3 · Answer 1 · edited May 23 '17 at 12:29

3

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.

edited May 23 '17 at 12:29

Community

1
1

answered Oct 23 '15 at 14:48

mat

40,498
3
51
78

2

s(X): I really dig `sublist//1`. How about writing `( [] | [L] )` instead of `( [] ; [L] )`? – repeat Oct 24 '15 at 09:48
1

I am in general *very much in favor* of using `|` in DCGs, +1! Probably it is more readable though when the variable is not exactly called `L`, isn't it? Compare `[] | [L]` or the even slightly less readable `[]|[L]` with `[] ; [L]` or `[];[L]`. Since I really would like to use `L` in this case, I find `;` slightly more readable in this concrete case. I would definitely use `|` in cases like `[] | [_]`. – mat Oct 25 '15 at 12:41
1

Got any data on the visual similarity of ASCII chars under difficult reading conditions? Sth like the jargon file "great runes", but not for uppercase vs lowercase, but uppercase vs uppercase. I guess "L" is bad when there may be any of "[|I_17" around (plus some more if we consider using *italics* for emphasizing sth)... – repeat Oct 25 '15 at 13:18
1

This would be extremely interesting! I currently have nothing formal about this. – mat Oct 25 '15 at 13:21
There's something to it, for sure! Just look at `[_I|Is]` *under difficult reading conditions*... Maybe the UX people could help: eyetracking plus skin conductance measurements, maybe? – repeat Oct 25 '15 at 16:05

CapelliC · Accepted Answer · 2015-10-23T14:28:02.047

1

I've found a not so elegant solution... it requires a cut and some builtins

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 noted by @Fatalize, we can avoid the cut, just forcing the empty list on first argument of 1^ clause:

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

I avoided to swap 2^ and 3^ clauses, so the 'natural' order is still nicely preserved

edited Oct 23 '15 at 14:28

answered Oct 23 '15 at 13:21

CapelliC

59,646
5
47
90

2

You don't need the cut if you use `assign([],[]).` instead of your first rule? If you want to get rid of the last evaluation which outputs `false` for some reason you can just swap the order of the second and third `assign` rules. It changes the ordering but is still valid according to what OP wants. – Fatalize Oct 23 '15 at 13:30
@Fatalize: the cut is required to avoid duplicate solutions, and the anon var to accept sublists of Xs – CapelliC Oct 23 '15 at 13:49
1

I don't get it. I obtain the exact same results with those changes. Care to provide an example which requires the cut and the anonymous variable? – Fatalize Oct 23 '15 at 13:56
1

Yeah it works! I'll make it the accepted answer, but I'll check back in a few days to look for something "more elegant" as you put it. – Mossmyr Oct 23 '15 at 14:11
@Fatalize: you're right, applying the changes you describe we get the solutions in inverse 'internal' order. – CapelliC Oct 23 '15 at 14:24

Length ordered subsets?

2 Answers2