I'm looking for a predicate that works as this:
?- subset([1,2,3], X).
X = [] ;
X = [1] ;
X = [2] ;
X = [3] ;
X = [1, 2] ;
X = [1, 2, 3] ;
X = [2, 3] ;
...
I've seen some subset implementations, but they all work when you want to check if one list is a subset of the another, not when you want to generate the subsets. Any ideas?
On http://www.probp.com/publib/listut.html you will find an implementation of a predicate called subseq0 that does what you want to:
subseq0(List, List).
subseq0(List, Rest) :-
subseq1(List, Rest).
subseq1([_|Tail], Rest) :-
subseq0(Tail, Rest).
subseq1([Head|Tail], [Head|Rest]) :-
subseq1(Tail, Rest).
A short explanation: subseq0(X, Y) checks whether Y is a subset subsequence of X, while subseq1(X, Y) checks whether Y is a proper subset subsequence of X.
Since the default representation of a set is a list with unique elements, you can use it to get all subsets as in the following example:
?- subseq0([1,2,3], X).
X = [1, 2, 3] ;
X = [2, 3] ;
X = [3] ;
X = [] ;
X = [2] ;
X = [1, 3] ;
X = [1] ;
X = [1, 2] ;
false.