4
\$\begingroup\$

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
\$\endgroup\$
2
  • 1
    \$\begingroup\$ 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'. \$\endgroup\$
    – user1149
    Sep 30, 2017 at 14:34
  • \$\begingroup\$ @BarryCarter could you elaborate on your solution? I am seriously interested. \$\endgroup\$
    – mcocdawc
    Oct 1, 2017 at 17:05

1 Answer 1

3
\$\begingroup\$
  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)
    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.

  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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.