CODEWITHSUNDEEP
prolog
hackermanwasd
hackermanwasd

Reputation: 95

Powerset o a set(list) in Prolog

I have the next predicate which will generate all subsets from a lists:

candidate([],[]).
candidate([H|T],[H|R]):-
    candidate(T,R).
candidate([_|T],R):-
    candidate(T,R).

Can somebody help me understand how it works? It looks so short but the recurrence behind it feels complicated to be understood.

Upvotes: 1

Views: 489

Answers (1)

slago
slago

Reputation: 5519

It's easy to see that the only subset of {} is {}.

candidate([], []).

Suppose you want to generate all subsets of the set S = {a,b,c}.

Then, you can remove an element from S (say element a), obtaining the set S-{a} = {b,c}.

By the induction hypothesis, you can generate all subsets of {b,c}, which are {}, {b}, {c}, {b,c}. That is done by the goal candidate(T, R).

Since every subset of {b,c} is also a subset of {a,b,c}, you can conclude that the subsets of S = {a,b,c} are:

  • {}, {b}, {c}, {b,c} (candidate([_|T],R) :- candidate(T,R)),

and also these same subsets joined with the set {a}, i.e.:

  • {a}, {a,b}, {a,c}, {a,b,c} (candidate([H|T],[H|R]) :- candidate(T,R)).

By altering the order of the two recursive rules, you can see this more clearly.

candidate([], []).
candidate([_|T], R):- candidate(T, R).     % does not include first element
candidate([H|T], [H|R]):- candidate(T,R).  % do include first element

Result:

?- candidate([a,b,c],S).
S = [] ;
S = [c] ;
S = [b] ;
S = [b, c] ;
S = [a] ;
S = [a, c] ;
S = [a, b] ;
S = [a, b, c].

Upvotes: 4

Related Questions