Generating Power Sets

For a given set \(S = \{a, b, c, ...\}\) we can generate the power set of \(S\) by iterating over the elements of \(S\) using the following algorithm:

The power set of the first element of \(S\):
This is just a set comprising of the empty set and the first element: \[\{\{\}, \{a\}\}\] Note that is has \(2^1\) elements.
The power set of the first two elements of \(S\):
This is the union of the set above with a set of unions of the second element \(b\) and the set above: \[\{\{\}, \{a\}\}\cup\{\{\}\cup\{b\}, \{a\}\cup\{b\}\}\] This simplifies to:
\[\{\{\}, \{a\}, \{b\}, \{a, b\}\}\] Note that it has \(2^2\) elements.
The power set of the first three elements of \(S\)
This is the union of the set above with a set of unions of the third element \(b\) and the set above: \[\{\{\}, \{a\}, \{b\}, \{a, b\}\}\cup\{\{c\},\{a,c\},\{b,c\},\{a,b,c\}\] This simplifies to:
\[\{\{\}, \{a\}, \{b\}, \{c\}, \{a, b\}, \{b, c\}, \{a, c\}, \{a, b, c\} \}\] Note that it has \(2^3\) elements.

And so on and so forth… Iterate until you reach the power set of \(S\).

Python Code to Generate Power Sets:

The below Python function generates a power set using the above algorithm.

def generate_power_set(set_input):
    """
    Generates the power set of an input set.
    :param set_input: the set to create a power set of
    :return: the power set of the input set
    """
    # sets are a collection of distinct objects. Coerce input into a set.
    set_input = set(set_input)
    # sets are not hashable/do not support indexing so we convert to a list temporarily
    set_input_list = sorted(set_input)
    # the power set of the first element is the empty set and the first element
    power_set_list = [(), (set_input_list[0],)]
    for index in range(1, len(set_input)):
        temp_list = []
        for each_set in power_set_list:
            temp_list.append(each_set + (set_input_list[index],))
        power_set_list = power_set_list + temp_list
    # convert back to a set
    power_set = set(power_set_list)
    return power_set
print(generate_power_set(("a", "b", "c")))
# power set of {"a", "b", "c"}

## {('b', 'c'), ('a', 'b', 'c'), ('b',), ('a',), ('a', 'c'), (), ('a', 'b'), ('c',)}

print(generate_power_set((1, 2, 2)))
# power set of {1, 2}

## {(1, 2), (2,), (), (1,)}

print(generate_power_set((2, 2, 2)))
# power set of {2}

## {(2,), ()}

print(generate_power_set((1, 2, 3, 4)))
# power set of {1, 2, 3, 4}

## {(1, 2), (1, 3), (1, 2, 3, 4), (1,), (2,), (3,), (1, 4), (1, 2, 3), (4,), (), (2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4), (3, 4), (2, 4)}