Compute power set of a given set in Python

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_sets.append(new_set)
power_set.extend(new_sets)

return power_set
• Cleverer way: loop from 0..2^n where n is the set size. Look at the binary representations, and include exactly those elements where the binary representation has a '1'. – Barry Carter Sep 30 '17 at 14:34
• @BarryCarter could you elaborate on your solution? I am seriously interested. – mcocdawc Oct 1 '17 at 17:05

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.

1. Redundant naming:

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

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

You could write for element in s

1. Names:

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

1. 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.

1. 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
1. 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)

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.

1. 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