4

I'm kinda new to Prolog. I'm trying to write a function subset(Set, Subset) that determines if Subset is a subset of Set (duh). Also, if the second parameter is not instantiated, it should output every possible subset. Right now, it works when both parameters are instantiated, but when I'm trying to output all subsets, it runs into a problem with member/2. For example:

?- subset([1,2,3], S).
S = [];
S = [1];
S = [1, 1];
S = [1, 1, 1];
...

Here is my code:

% subset/2
% subset(Set, Subset) iff Subset is a subset of Set
subset(_, []).
subset(Set, [H|T]) :-
  member(H, Set),
  subset(Set, T).

How do I make it so that member doesn't keep picking the first option in Set?

Matthew
  • 1,905
  • 3
  • 19
  • 26
Chris Phillips
  • 233
  • 3
  • 13
  • 3
    "(duh)": it is quite confusing to have such a name: Consider `set_subset(Set, Subset)` in stead. – false Nov 22 '14 at 22:28
  • 3
    Note that the `iff` in your comment is not accurate, because `Set = any, Subset = []` and many more. Instead, say simply `if` – false Nov 22 '14 at 22:51
  • Possible duplicate of [Subsets in Prolog](https://stackoverflow.com/questions/4912869/subsets-in-prolog) –  Jun 05 '17 at 18:09

2 Answers2

4

(Many Prolog systems including SICStus and SWI have a subset/2 in their library, but rather subset(Subset, Set) ; and it is also not a clean relation...)

It all depends on what you mean by a set. Is [1, 1] a valid set? Do they have to occur in one order or the other? Your definition is fine, if you permit duplicates. After all your definition reads:

set_subset(Set, Subset): All elements of Subset are elements of Set

What you are rather surprised about is that you have now an infinite set of solutions. And, even worse, that set is enumerated in a very unfair manner. If it is only the precise order solutions are enumerated that you worry, consider:

?- length(Subset,N), set_subset([1,2,3], Subset).
   Subset = [], N = 0
;  Subset = [1], N = 1
;  Subset = [2], N = 1
;  Subset = [3], N = 1
;  Subset = [1, 1], N = 2
;  Subset = [1, 2], N = 2
;  Subset = [1, 3], N = 2
;  Subset = [2, 1], N = 2
;  Subset = [2, 2], N = 2
;  Subset = [2, 3], N = 2
;  false.

If you want that Subset has finitely many solutions, you probably want rather a subsequence. See this answer.

false
  • 10,264
  • 13
  • 101
  • 209
  • 1
    @j4nbur53: Please note the last sentence! – false Jun 04 '17 at 07:37
  • 1
    @j4nbur53: Please reread my answer: It's about OP's solution! – false Jun 04 '17 at 11:31
  • 1
    @j4nbur53: OP asked: "basically, how do I make it so that member doesn't keep picking the first option in Set? " – false Jun 04 '17 at 12:27
  • 1
    @j4nbur53: Sorry, I addressed this problem in my answer. And it has nothing to do with unnecessary choice points, it's just the cardinality of the set of solutions. – false Jun 04 '17 at 12:32
2

To enumerate subsets, I don't think its necessary to also generate permutations, after all a set shouldn't care about ordering. So the typical text book solution is:

% subset(-Set, +Set)
subset([X|L], [X|R]) :-
   subset(L, R).
subset(L, [_|R]) :-
   subset(L, R).
subset([], []).

Compare this with the other solutions:

This solution:

?- subset(X, [1,2,3]), write(X), nl, fail; true.
[1,2,3]
[1,2]
[1,3]
[1]
[2,3]
[2]
[3]
[]

The others capellis solution:

?- subset([1,2,3], X), write(X), nl, fail; true.
[]
[1]
[1,2]
[1,2,3]
[1,3]
[1,3,2]
[2]
[2,1]
[2,1,3]
[2,3]
[2,3,1]
[3]
[3,1]
[3,1,2]
[3,2]
[3,2,1]

From set theory we know |P(A)|=2^|A|, so for 3 element long input subset should generate 8 subsets. This is what this solution does, but other solutions enumerate way to many redundant subsets.

  • 2
    You are giving the definition of a subsequence with reversed arguments. That includes again many redundant solutions as in `subset(X, [a,a,a])`. – false Jun 04 '17 at 07:36
  • There are no multi-sets in Prolog either, viz. `[1,2]` and `[2,1]`. – false Mar 24 '19 at 14:26
  • If you want non-redundant solutions, you need to call `sort([a,a,a], Y), subset(X, Y)`, the subset/2 predicate doesn't change in any way. sort/2 is part of the ISO core standard. –  Mar 24 '19 at 18:44
  • In Jekejeke Prolog instead of sort/2, you could also use sys_distinct/2. This predicate tries to preserve the input order, and removes duplicates. See also: https://github.com/jburse/jekejeke-devel/blob/master/jekrun/headless/jekpro/frequent/standard/sort.p#L77 –  Mar 24 '19 at 18:50