Compute power set of a given set in Python

Question

Problem:

Given a set (let's say of integers), return the list of all of its subsets also known as the power set.

It looks to be working, but I would like feedback on the algorithm and Python coding style and techniques as I am new to Python.

def get_power_set(s):

    empty_set = set()
    power_set = [empty_set]

    for elem in s:
        # Need this temporary list because we can't change the power_set list while iterating it. Or so I think.
        new_sets = [] 
        for power_set_item in power_set:
            new_set = set().union(power_set_item) # Is this the best way to copy set?
            new_set.add(elem)
            new_sets.append(new_set)
        power_set.extend(new_sets)

    return power_set

Answer 1

1. Find the appropriate datatype for your problem.

This is actually a problem in the task. The power set is by definition a set. You use even the variable name power_set so actually it is quite surprising, that it is a list and not a set.

2. Redundant naming:

It is obvious, that set() is an empty set: Better use: power_set = [set()]

3. Don't abbreviate if it is not necessary:

You could write for element in s

4. Names:

Naming stuff is the hardest part. But I would call a power_set_item simply a subset.

5. Operators

This is open for debate and perhaps just my taste, but I would use | instead of the union method. This also means to use |= and += instead of update and extend.

6. Copy

In general the best way to copy is to call the copy method: new_set = power_set_item.copy(). But in your case it is important to note, that | and .union return a new set, so you could write:

new_sets.append(subset | {element})

All points combined yield the following code:

def get_power_set(s):

    power_set = [set()]

    for element in s:
        new_sets = [] 
        for subset in power_set:
            new_sets.append(subset | {element})
        power_set.extend(new_sets)

    return power_set

7. List Comprehension:

As you wrote in your comment, you don't like the new_sets variable. You can easily get rid of it, by using list comprehensions. In general if you have code like:

A = []
for j in B:
    x = do_stuff(j)
    A.add(x)

Always check if you can't write it in the following way:

A = [do_stuff(j) for j in B]

This gives now the following improvement:

def get_power_set(s):

    power_set = [set()]

    for element in s:
        one_element_set = {element}
        power_set += [subset | one_element_set for subset in power_set]

    return power_set

The line with one_element_set = {element} is to prevent the potentially costly repeated creation of a new object.

8. Datatype

To come back to the first point. If we take the previous code we can easily change it, to return a set of frozensets:

def get_power_set(s):

    power_set = {frozenset()}

    for element in s:
        one_element_set = frozenset({element})
        power_set |= {subset | one_element_set for subset in power_set}

    return power_set