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

## What is the Powerset of 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}}

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.

## The Code

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

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

Guess the output of this code snippet!

## How It Works

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 adding 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]]

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