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.



Task

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

 {{}, {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}}.
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):


 





P




{\displaystyle {\mathcal {P}}}

(



∅


{\displaystyle \varnothing }

) = { 



∅


{\displaystyle \varnothing }

 }

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


 





P




{\displaystyle {\mathcal {P}}}

({



∅


{\displaystyle \varnothing }

}) = { 



∅


{\displaystyle \varnothing }

, { 



∅


{\displaystyle \varnothing }

 } }


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




SIMSET
BEGIN
 
    LINK CLASS LOF_INT(N); INTEGER N;;
 
    LINK CLASS LOF_LOF_INT(H); REF(HEAD) H;;
 
    REF(HEAD) PROCEDURE MAP(P_LI, P_LLI);
        REF(HEAD) P_LI;
        REF(HEAD) P_LLI;
    BEGIN
        REF(HEAD) V_RESULT;
        V_RESULT :- NEW HEAD;
        IF NOT P_LLI.EMPTY THEN BEGIN
            REF(LOF_LOF_INT) V_LLI;
            V_LLI :- P_LLI.FIRST QUA LOF_LOF_INT;
            WHILE V_LLI =/= NONE DO BEGIN
                REF(HEAD) V_NEWLIST;
                V_NEWLIST :- NEW HEAD;
                ! ADD THE SAME 1ST ELEMENT TO EVERY NEWLIST ;
                NEW LOF_INT(P_LI.FIRST QUA LOF_INT.N).INTO(V_NEWLIST);
                IF NOT V_LLI.H.EMPTY THEN BEGIN
                    REF(LOF_INT) V_LI;
                    V_LI :- V_LLI.H.FIRST QUA LOF_INT;
                    WHILE V_LI =/= NONE DO BEGIN
                        NEW LOF_INT(V_LI.N).INTO(V_NEWLIST);
                        V_LI :- V_LI.SUC;
                    END;
                END;
                NEW LOF_LOF_INT(V_NEWLIST).INTO(V_RESULT);
                V_LLI :- V_LLI.SUC;
            END;
        END;
        MAP :- V_RESULT;
    END MAP;
 
    REF(HEAD) PROCEDURE SUBSETS(P_LI);
        REF(HEAD) P_LI;
    BEGIN
        REF(HEAD) V_RESULT;
        IF P_LI.EMPTY THEN BEGIN
            V_RESULT :- NEW HEAD;
            NEW LOF_LOF_INT(NEW HEAD).INTO(V_RESULT);
        END ELSE BEGIN
            REF(HEAD) V_SUBSET, V_MAP;
            REF(LOF_INT) V_LI;
            V_SUBSET :- NEW HEAD;
            V_LI :- P_LI.FIRST QUA LOF_INT;
            ! SKIP OVER 1ST ELEMENT ;
            IF V_LI =/= NONE THEN V_LI :- V_LI.SUC;
            WHILE V_LI =/= NONE DO BEGIN
                NEW LOF_INT(V_LI.N).INTO(V_SUBSET);
                V_LI :- V_LI.SUC;
            END;
            V_RESULT :- SUBSETS(V_SUBSET);
            V_MAP :- MAP(P_LI, V_RESULT);
            IF NOT V_MAP.EMPTY THEN BEGIN
                REF(LOF_LOF_INT) V_LLI;
                V_LLI :- V_MAP.FIRST QUA LOF_LOF_INT;
                WHILE V_LLI =/= NONE DO BEGIN
                    NEW LOF_LOF_INT(V_LLI.H).INTO(V_RESULT);
                    V_LLI :- V_LLI.SUC;
                END;
            END;
        END;
        SUBSETS :- V_RESULT;
    END SUBSETS;
 
    PROCEDURE PRINT_LIST(P_LI); REF(HEAD) P_LI;
    BEGIN
        OUTTEXT("[");
        IF NOT P_LI.EMPTY THEN BEGIN
            INTEGER I;
            REF(LOF_INT) V_LI;
            I := 0;
            V_LI :- P_LI.FIRST QUA LOF_INT;
            WHILE V_LI =/= NONE DO BEGIN
                IF I > 0 THEN OUTTEXT(",");
                OUTINT(V_LI.N, 0);
                V_LI :- V_LI.SUC;
                I := I+1;
            END;
        END;
        OUTTEXT("]");
    END PRINT_LIST;
 
    PROCEDURE PRINT_LIST_LIST(P_LLI); REF(HEAD) P_LLI;
    BEGIN
        OUTTEXT("[");
        IF NOT P_LLI.EMPTY THEN BEGIN
            INTEGER I;
            REF(LOF_LOF_INT) V_LLI;
            I := 0;
            V_LLI :- P_LLI.FIRST QUA LOF_LOF_INT;
            WHILE V_LLI =/= NONE DO BEGIN
                IF I > 0 THEN BEGIN
                    OUTTEXT(",");
                !   OUTIMAGE;
                END;
                PRINT_LIST(V_LLI.H);
                V_LLI :- V_LLI.SUC;
                I := I+1;
            END;
        END;
        OUTTEXT("]");
        OUTIMAGE;
    END PRINT_LIST_LIST;
 
    INTEGER N;
    REF(HEAD) V_RANGE;
    REF(HEAD) V_LISTS;
 
    V_RANGE :- NEW HEAD;
    V_LISTS :- SUBSETS(V_RANGE);
    PRINT_LIST_LIST(V_LISTS);
    OUTIMAGE;
    FOR N := 1 STEP 1 UNTIL 4 DO BEGIN
        NEW LOF_INT(N).INTO(V_RANGE);
        V_LISTS :- SUBSETS(V_RANGE);
        PRINT_LIST_LIST(V_LISTS);
        OUTIMAGE;
    END;
END.
 