Subsets in Prolog

问题:

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?

回答1:

Here goes an implementation:

subset([], []).
subset([E|Tail], [E|NTail]):-
  subset(Tail, NTail).
subset([_|Tail], NTail):-
  subset(Tail, NTail).

It will generate all the subsets, though not in the order shown on your example.

As per commenter request here goes an explanation:

The first clause is the base case. It states that the empty list is a subset of the empty list.

The second and third clauses deal with recursion. The second clause states that if two lists have the same Head and the tail of the right list is a subset of the tail of the left list, then the right list is a subset of the left list.

The third clause states that if we skip the head of the left list, and the right list is a subset of the tail of the left list, then the right list is a subset of the left list.

The procedure shown above generates ordered sets. For unordered sets you might use permutation/3:

unordered_subset(Set, SubSet):-
  length(Set, LSet),
  between(0,LSet, LSubSet),
  length(NSubSet, LSubSet),
  permutation(SubSet, NSubSet),
  subset(Set, NSubSet).

回答2:

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.

回答3:

Set is a collection of distinct objects by definition. A subset procedure shouldn't care about the order of elements in the set(in the arguments). A proper solution(swi prolog) may look like:

subset(_, []).
subset([X|L], [A|NTail]):-
    member(A,[X|L]),    
    subset(L, NTail),
    not(member(A, NTail)).

For the question ?- subset([1,2,3], E) it will generate:

E = [] ;
E = [1] ;
E = [1, 2] ;
E = [1, 2, 3] ;
E = [1, 3] ;
E = [2] ;
E = [2, 3] ;
E = [3] ;
E = [3, 2] ;
false.

Hope it will help!

回答4:

we can also test by deleting subset's item from the super set.

% to delete : an item can be deleted it its in the head or in the tail of a list
delete(I,[I|L],L).
delete(I,[H|L],[H|NL]) :- delete(I,L,NL).
% an [] is an item of an set.A set is a subset of we can recursively delete its head item from the super set.
subset(_,[]).
subset(S,[I|SS]) :- delete(I,S,S1), subset(S1,SS).

example:

subset([a,b,c],S).
S = []
S = [a]
S = [a, b]
S = [a, b, c]
S = [a, c]
S = [a, c, b]
S = [b]
S = [b, a]
S = [b, a, c]
S = [b, c]
S = [b, c, a]
S = [c]
S = [c, a]
S = [c, a, b]
S = [c, b]
S = [c, b, a] 

---

subset([a,b,a,d,e],[a,e]).
1true

回答5:

append([],L,L).

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


subset([X|T],[X|L]) :-subset(T,L).

subset([X|T],[G|L]) :-subset([X],L),append(L2,[X|L3],[G|L]),append(L2,L3,L4),subset(T,L4).

subset([],_).

----------------------------------------------
?- subset([1,2],[1,2]).

yes

?- subset([1,2],[2,1]).

yes

?- subset([1,1],[1,2]).

no

?- subset(D,[1,2]).

D = [1,2] ;

D = [1] ;

D = [2,1] ;

D = [2] ;

D = '[]' ;

no