Subsets in Prolog

Question

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?

You should switch the arguments in the subset(X, Y) predicate so that we naturally read X is a subset of Y, not like you did: Y is a subset of X. — Dávid Natingga, Mar 01 '14 at 10:39

gusbro · Answer 1 · 2012-08-14T16:37:07.590

31

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

edited Aug 14 '12 at 16:37

answered Feb 06 '11 at 23:47

gusbro

22,357
35
46

Could you explain the third rule? I don't quite understand it's purpose. – Jordan Scales Aug 13 '12 at 18:29
1

This only works with sorted sets I take it? `subset([2,1], [1,2,3]).` says no. – Jordan Scales Aug 14 '12 at 01:57
1

@JordanScales: Your example is switching arguments, it should read `subset([1,2,3],[2,1])` which indeed will answer false as the procedure generates ordered subsets. You might use `unordered_subset/3` (added to the answer) instead. – gusbro Aug 14 '12 at 16:39
@gusbro That's the same code I wrote when I first started learning Prolog. For some odd reason it doesn't work with SWI-Prolog 7.2.3. During backtracking SWI-Prolog repeatedly appends an unbound variable during redo of the second clause, for the Tail variable, and backtracking never ends. – Robert Oschler Jan 20 '17 at 17:23

score 8 · Answer 2 · edited Jan 03 '16 at 08:28

8

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.

edited Jan 03 '16 at 08:28

repeat

18,496
4
54
166

answered Feb 06 '11 at 11:39

Nubok

3,502
7
27
47

3

This generates subsequences, not subsets. That's the same when working with sorted lists of unique elements, though. – Fred Foo Feb 06 '11 at 13:50
1

You are basically right (corrected it). But why do you require the list to be sorted? – Nubok Feb 06 '11 at 14:01
you're right, it will also work when the list is not sorted, just `uniq`'d. But the easiest way to get unique elements is through `sort/2` :) – Fred Foo Feb 07 '11 at 14:50

score 2 · Answer 3 · answered Jan 01 '16 at 14:06

2

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!

answered Jan 01 '16 at 14:06

ostruk

69
4

1

`subset([A,B],[C,D]).` fails. It should succeed. – false Jan 01 '16 at 19:09
@false [C,D] is not a subset of [A,B] it is suppose to fail – Bao Thai Apr 25 '17 at 03:35
2

@BaoThai: It certainly is a subset (with answer substitution `A = C, B = D ; A = D, B = C`) – false Apr 25 '17 at 09:30
1

@BaoThai: While `subset([A], [B])` succeeds with `A = B`, above fails. – false Apr 25 '17 at 09:32
1

@BaoThai: Even `subset([A,B],[A,B]).` fails, can we agree at least that this is wrong? – false Apr 25 '17 at 13:53

score 1 · Answer 4 · answered Oct 11 '18 at 00:34

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

This solution returns both `[a, b]` and `[b, a]`, when, in fact, the order of the elements is not relevant and only one of them should be listed as a subset as they represent the same set. — Milos, Nov 30 '18 at 18:24

score -2 · Answer 5 · edited Mar 04 '16 at 14:04

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

Subsets in Prolog

5 Answers5

Linked