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

• user1149: 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'.
• mcocdawc: @BarryCarter could you elaborate on your solution? I am seriously interested.

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