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

Table of Contents

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

**But before we move on, I’m excited to present you 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).

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

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

While working as a researcher in distributed systems, Dr. Christian Mayer found his love for teaching computer science students.

To help students reach higher levels of Python success, he founded the programming education website Finxter.com. He’s author of the popular programming book Python One-Liners (NoStarch 2020), coauthor of the Coffee Break Python series of self-published books, computer science enthusiast, freelancer, and owner of one of the top 10 largest Python blogs worldwide.

His passions are writing, reading, and coding. But his greatest passion is to serve aspiring coders through Finxter and help them to boost their skills. You can join his free email academy here.