Python Powerset

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

This is a simple algorithm to find all powersets of a given set.

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

Leave a Comment