Generating subsets using length/2 and ord_subset/2

Question

I am a beginner in prolog. I tried this in swipl interpreter:

?- length(Lists, 3), ord_subset(Lists, [1, 2, 3, 4]).
false.

expecting to get all length-3 lists that are subsets of [1, 2, 3, 4] like [1, 2, 3] or [1, 2, 4]. Why do i get false?

Notice: both length and ord_subset are builtin functions (or whatever they are called) in SWI-Prolog.

Answer 1

You don't get a solution because the ord_subset/2 predicate only checks if a list is a subset of another list; it does not generate subsets.

Here is one simplistic way to define a predicate that does what you seem to be after:

subset_set([], _).
subset_set([X|Xs], S) :-
    append(_, [X|S1], S),
    subset_set(Xs, S1).

This assumes that these are "ordsets", that is, sorted lists without duplicates.

You will notice that the subset happens to be also a subsequence. We could have written instead:

subset_set(Sub, Set) :-
    % precondition( ground(Set) ),
    % precondition( is_list(Set) ),
    % precondition( sort(Set, Set) ),
    subseq_list(Sub, Set).

subseq_list([], []).
subseq_list([H|T], L) :-
    append(_, [H|L1], L),
    subseq_list(T, L1).

With either definition, you get:

?- length(Sub, 3), subset_set(Sub, [1,2,3,4]).
Sub = [1, 2, 3] ;
Sub = [1, 2, 4] ;
Sub = [1, 3, 4] ;
Sub = [2, 3, 4] ;
false.

You can even switch the order of the two subgoals in the example query, but this is probably the better way to write it.

However, the second argument must be ground; if it is not:

?- subset_set([A,B], [a,B]), B = a.
A = B, B = a ; Not a real set, is it?
false.