Search code examples
prolog

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.

Solution

  • 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].