[Python Powerset] How To Get All Subsets of a Set?

by

This is a simple algorithm to find all the powersets of a given set. If you feel like you need to refresh your Python set skills, have a look at my complete guide to Python sets (with Harry Potter examples).

Problem Formulation: Powerset

What is the powerset of a given set s?

The powerset is the set of all subsets of the given set s.

A subset is a set that includes an arbitrary number of elements of the original set s. It includes both the empty set {} and the given set s.

Have a look at the following examples:

Example 1:

  • Given set: s = {1}                            
  • Powerset: P = {{},{1}}

Example 2:

  • Given set: s = {1, 2}                      
  • Powerset: P = {{},{1},{2},{1,2}}

Example 3:

  • Given set: s = {1, 2, 3}                
  • Powerset: P = {{},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}

Iterative Algorithm Idea

In the previous examples, can you already see the pattern of how to construct the powerset in an iterative manner?

To calculate a powerset P of a set s with n elements, simply calculate the powerset P' of a subset of s with (n-1) elements and add the n-th element to each set in the powerset P'.

Now merge the resulting set of sets with the previous powerset P' and you get the powerset P.

In other words, start with the empty set {} and put it into a temporary set of sets P'. Now go over all elements x in s. For each element x and each set p in P', create a new subset that consists of the union of x and p.

This strategy will be explained in detail in the following.

Powerset as a Python One-Liner

We consider the following problem: Create a one-liner solution that calculates the powerset of a given set s.

Here’s the code, we’ll explain it right afterwards:

# Dependencies
from functools import reduce


# The Data
s = {1, 2, 3}


# The One-Liner
ps = lambda s: reduce(lambda P, x: P + [subset | {x} for subset in P], s, [set()])


# The Result
print(ps(s))

Listing: One-liner solution using basic array arithmetic.

🧩 Exercise: Guess the output of this code snippet!

The one-liner shows an elegant way to solve the problem of calculating the powerset.

The idea is to start the powerset as an empty set and repeatedly add subsets to it until no more subsets can be found.

Initially, only the empty set is in the powerset.

Now, in each step, we take one element x out of the dataset s and create a bunch of new subsets that naturally emerge by adding x to all subsets that are already in the powerset. Hence, the size of the powerset doubles each time we add a new element x.

In this way, we can grow the powerset one element at-a-time.

The one-liner uses the reduce() function to accomplish this idea. It maintains the current powerset in the variable P (which initially contains only the empty set).

Using list comprehension, it creates new subsets – one for each existing subset – and adds them to the powerset P. In particular, it adds the value x from the dataset to each subset and thus doubles the size of the powerset (containing the subsets with and without the dataset element x).

In this way, the reduce() function repeatedly “merges” two elements: the powerset P and an element x from the dataset.

Hence, the result of the one-liner is the following:

# The Result
print(ps(s))
# [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

This article is based on a book section of my 2021 NoStarch book. I’ll show you more ways to calculate the powerset in a moment.

Check out my new Python book Python One-Liners (Amazon Link).

If you like one-liners, you’ll LOVE the book. It’ll teach you everything there is to know about a single line of Python code. But it’s also an introduction to computer science, data science, machine learning, and algorithms. The universe in a single line of Python!

The book was released in 2020 with the world-class programming book publisher NoStarch Press (San Francisco).

Publisher Link: https://nostarch.com/pythononeliners

Python Powerset Itertools

To calculate the powerset, you can use the itertools library as follows:

  • Import the chain and combinations submodules.
  • Use a generator expression combinations(s, r) for r in range(len(s)+1) to generate all combinations of r-length subsequences of s for all possible values of r. Learn more about the combinations function here.
  • Merge all those into a single list by using the chain.from_iterable() function around the previous generator expression.
from itertools import chain, combinations

def powerset(iterable):
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))


results = list(powerset(['alice', 'bob', 'carl']))
print(results)
# [(), ('alice',), ('bob',), ('carl',), ('alice', 'bob'), ('alice', 'carl'), ('bob', 'carl'), ('alice', 'bob', 'carl')]

Reference: You can learn more about this idea here.

Python Powerset Recursive

The following algorithm recursively calculates the powerset recursively:

  • Recursion base case: If the initial list is empty, it returns the trivial “powerset” [[]].
  • Recursive computation: If the initial list is non-empty, recursively calculate the powerset of the sublist starting from the second element.
  • Building the higher-level solution: Create a second list of sublists by adding the first element to each element in the recursively-created powerset. Now, combine both optained lists to the powerset.
def powerset(lst):
    if not lst:
        return [[]]
    exclude_first = powerset(lst[1:])
    include_first = [[lst[0]] + x for x in exclude_first]
    return exclude_first + include_first


s = powerset(['alice', 'bob', 'carl'])
print(s)
# [[], ['carl'], ['bob'], ['bob', 'carl'], ['alice'], ['alice', 'carl'], ['alice', 'bob'], ['alice', 'bob', 'carl']]

Note that you can easily modify the resulting list of list into a set of tuples to more appropriately represent the “powerset” data structure.

Where to Go From Here?

To thrive in Python, you need to understand the basics such as lambda functions, list comprehension, and set operations. They are the basic building blocks of your advanced code understanding and coding productivity.

Puzzle-based learning is one of the best ways to keep your eye trained as a Python programmer — so that you can quickly understand any given code snippet you read. That’s one of the most important coding skills there is!

To train your skills the fun way, consider becoming lifetime Finxter premium member and reach Python freelancer level. So that you can support yourself and your family by working from the comfort of your home. The formula for your new high-income skill is simple:

YOU + YOUR COMPUTER + PYTHON = BE YOUR OWN BOSS