A power set is the set of all possible subsets of a set. For example, if we have a set containing [A, B, C] the possible subsets are:

[[], ['A'], ['B'], ['A', 'B'], ['C'], ['A', 'C'], ['B', 'C'], ['A', 'B', 'C']]

Note that I am not using actual set notation here, which would look like this: {A, B, C}, since we will be working with Python lists to represent sets in much of this article. To learn more about power sets themselves, check out this page on Maths is Fun.

Have a go at writing a Python program that finds the power set of {A, B, C}. You will get much more from this article if you have made an attempt at solving the problem for yourself before reading on.

Efficient Python Code for Finding Power Sets

If you simply need to find the power set of a given set using Python, and are not interested how the code works, one of the best ways is as follows:

import itertools


def power_set(the_set):
    for subset in itertools.product(*[[[], [i]] for i in the_set]):
        yield {j for i in subset for j in i}


my_set = {"A", "B", "C"}
print(list(power_set(my_set)))

Output:

[set(), {'B'}, {'C'}, {'C', 'B'}, {'A'}, {'A', 'B'}, {'A', 'C'}, {'A', 'C', 'B'}]

This makes use of the itertools built-in module in python, and is quite a fast solution.

A More Understandable way to Find Power Sets with Python

One way to think about a power set is to consider all the possible permutations of including and excluding the elements of the set. An example is shown in the table below.

This insight gives us a way to go about writing a program to find power sets. Now that you have this insight, you may want to try to implement a solution based on it before reading on…

The solution below makes use of Python’s arithmetic right-shift operator: >>. You can read more about bitwise operators in Python here. The key to the algorithm we are going to use is this:

10 >> 2 
2 # Same as integer division by 2

13 >> 2
3 # Same as integer division by 2 - Notice the final bit is discarded

Keeping this behaviour in mind, see if you can make sense of the following output from a nested for loop which we will be using:

i: 0, j: 0, i >> j: 0
i: 0, j: 1, i >> j: 0
i: 0, j: 2, i >> j: 0

i: 1, j: 0, i >> j: 1
i: 1, j: 1, i >> j: 0
i: 1, j: 2, i >> j: 0

i: 2, j: 0, i >> j: 2
i: 2, j: 1, i >> j: 1
i: 2, j: 2, i >> j: 0

i: 3, j: 0, i >> j: 3
i: 3, j: 1, i >> j: 1
i: 3, j: 2, i >> j: 0

i: 4, j: 0, i >> j: 4
i: 4, j: 1, i >> j: 2
i: 4, j: 2, i >> j: 1

i: 5, j: 0, i >> j: 5
i: 5, j: 1, i >> j: 2
i: 5, j: 2, i >> j: 1

i: 6, j: 0, i >> j: 6
i: 6, j: 1, i >> j: 3
i: 6, j: 2, i >> j: 1

i: 7, j: 0, i >> j: 7
i: 7, j: 1, i >> j: 3
i: 7, j: 2, i >> j: 1

Don’t worry if you can’t see what those values have to do with the problem. Just have a little ponder, before we move on. In particular think about what % applied to the result of dividing by 2 might have to do with the problem, bearing in mind anything you know about an algorithm for converting decimal numbers to binary.

OK, so now for an “understandable but not the most efficient” solution to finding power sets with Python:

def power_set(elements):
    n = len(elements)
    result = []
    # For each of the 2^n possible permutations of binary digits from 0 to n - 1
    for i in range(2 ** n):
        subset = []
        for j in range(n):
            # Check jth bit of binary representation of integer i
            print(f"i: {i}, j: {j}, i >> j: {i >> j}")
            if (i >> j) % 2 == 1:
                subset.append(elements[j])
        print()
        result.append(subset)
    return result


A = ["A", "B", "C"]
print(list(power_set(A)))

Output:

[[], ['A'], ['B'], ['A', 'B'], ['C'], ['A', 'C'], ['B', 'C'], ['A', 'B', 'C']]

So what’s going on here? If you trace through the algorithm using one of the various methods for doing so, such as here: How to trace python algorithms with a visualisation tool, you will get a sense of what is going on. From the table shown earlier on, we can see quite easily why there needs to be 2^n iterations – these represents all the possible permutations of binary bits to represent set elements. The nested for loop basically checks each bit of the binary representation of the outer loop counter to determine whether to include or exclude the current element.

Check out these Books on Learning Algorithms and Data Structures

Please note, as an Amazon Associate I earn from qualifying purchases.

Other Approachs to finding Power Sets with Python

There are many different ways of implementing a solution to the problem of finding power sets with Python. If you are into this kind of thing, you will find it very instructive to explore different approaches and to see what each reveals about the problem and about algorithmic thinking. Many of the solutions you will find on the internet are recursive in nature, which makes intuitive sense if you are used to thinking about problems in this way. You will also find a lot of variation in the efficiency of various approaches. This also provides an opportunity to develop your algorithmic thinking and understanding of time complexity. All in all the topic of generating power sets can be a very rich field of enquiry.

This article has explored the problem of finding the power set of a given set using Python. I hope you have found it interesting and helpful.

Happy computing!

Sharing is caring!