Problem Statement

A   set   is a collection (container) of certain values, without any particular order, and no repeated values. It corresponds with a finite set in mathematics. A set can be implemented as an associative array (partial mapping) in which the value of each key-value pair is ignored. Given a set S, the power set (or powerset) of S, written P(S), or 2S, is the set of all subsets of S.

By using a library or built-in set type, or by defining a set type with necessary operations, write a function with a set S as input that yields the power set 2S of S.

For example, the power set of     {1,2,3,4}     is For a set which contains n elements, the corresponding power set has 2n elements, including the edge cases of empty set. The power set of the empty set is the set which contains itself (20 = 1): And the power set of the set which contains only the empty set, has two subsets, the empty set and the set which contains the empty set (21 = 2):

Extra credit: Demonstrate that your language supports these last two powersets.

Let's start with the solution:

:- object(set).

    :- public(powerset/2).

    powerset(Set, PowerSet) :-
        reverse(Set, RSet),
        powerset_1(RSet, [[]], PowerSet).

    powerset_1([], PowerSet, PowerSet).
    powerset_1([X| Xs], Yss0, Yss) :-
        powerset_2(Yss0, X, Yss1),
        powerset_1(Xs, Yss1, Yss).

    powerset_2([], _, []).
    powerset_2([Zs| Zss], X, [Zs, [X| Zs]| Yss]) :-
        powerset_2(Zss, X, Yss).

    reverse(List, Reversed) :-
        reverse(List, [], Reversed).

    reverse([], Reversed, Reversed).
    reverse([Head| Tail], List, Reversed) :-
        reverse(Tail, [Head| List], Reversed).

:- end_object.


| ?- set::powerset([1, 2, 3, 4], PowerSet).

PowerSet = [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3],[4],[1,4],[2,4],[1,2,4],[3,4],[1,3,4],[2,3,4],[1,2,3,4]]
yes