# How to Find Powerset in Python

Hemank Mehtani Feb 12, 2024

In mathematics, a power set of any set is a set that contains all the possible subsets of a given set along with an empty set.

In other words, all subsets of a set are also known as a power set. There can be a power set of lists, sets, and strings in Python.

In this tutorial, we will find the power set of a given set in Python using various methods.

## Use the Iterative Approach to Get a Power Set in Python

The iterative approach to obtaining a power set involves generating all possible subsets of a given set by iteratively building the power set. Though we can use both the recursive approach and the iterative approach to find a power set, the iterative approach is preferred over the recursive as it is a faster process.

In this method, we use a nested `for` loop to create such a power set.

For example,

``````def powerset(fullset):
listsub = list(fullset)
subsets = []
for i in range(2 ** len(listsub)):
subset = []
for k in range(len(listsub)):
if i & 1 << k:
subset.append(listsub[k])
subsets.append(subset)
return subsets

subsets = powerset(set([1, 2, 3, 4]))
print(subsets)
print(len(subsets))
``````

In the `listsub = list(fullset)` line, the input set (`fullset`) is converted to a list (`listsub`). This is done to facilitate indexing and iteration.

For subset generation, in the `for i in range(2 ** len(listsub)):` code, the outer loop iterates through all numbers from `0` to `2^len(listsub) - 1`. Each number corresponds to a unique combination of including or excluding elements from the original set.

An empty list `subset` is initialized for each iteration to store the current subset. The inner loop in the code, `for k in range(len(listsub))`, iterates through the elements of the original set.

Next, the `if i & 1 << k:` code checks if the `k`-th bit is set in the binary representation of `i`. If true, it means the corresponding element from the set should be included in the subset.

If the condition is met in the `subset.append(listsub[k])` code, the element is added to the current subset. Lastly, the generated subset is appended to the `subsets` list.

Output:

``````[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3], [4], [1, 4], [2, 4], [1, 2, 4], [3, 4], [1, 3, 4], [2, 3, 4], [1, 2, 3, 4]]
16
``````

The provided set (`{1, 2, 3, 4}`) outputs all the possible subsets and the total count of subsets which is 16.

## Use the `itertools.combinations` Function to Find a Power Set in Python

The `itertools` is a module in Python used to iterate over data structures.

These data structures are also known as iterables. They can be stepped over by using a `for` loop.

The `combinations` function from this module can create combinations of a set to create a power set.

For example,

``````from itertools import combinations

def powerset(string):
n = len(string)
for i in range(0, n + 1):
for element in combinations(string, i):
print("".join(element))

string = ["x", "y", "z"]
powerset(string)
``````

In this method, we start by importing the `combinations` function from the `itertools` module. We also define a function named `powerset` that takes an iterable `string` as input.

The `n = len(string)` calculates the length of the input iterable (`string`).

For the nested loop, `for i in range(0, n + 1):`, the outer loop iterates over all possible lengths of subsets, from 0 to the length of the input iterable (`string`). Then, the `for element in combinations(string, i):` line is the inner loop that uses the `combinations` function to generate all combinations of length `i` from the input iterable (`string`).

Lastly, the `print("".join(element))` will be printing each combination after joining its elements into a string.

Note: The use of `"".join(element)` is specific to strings; if the original elements were not strings, this line might need modification.

Output:

``````
x
y
z
xy
xz
yz
xyz
``````

As the variable string has its values `string = ["x", "y", "z"] `, it will output all possible combinations of the elements `x`, `y`, and `z` at different lengths, including the empty subset.

## Use the List Comprehension Method to Find a Power Set in Python

List Comprehension is a way to create new lists based on the existing list. It offers a shorter syntax, being more compact and faster than the other functions and loops used for creating a list.

We can also use list comprehension to find a power set in Python by utilizing a nested `for` loop.

For example,

``````def get_subsets(fullset):
listrep = list(fullset)
n = len(listrep)
return [[listrep[k] for k in range(n) if i & 1 << k] for i in range(2**n)]

string = ["x", "y", "z"]
print(get_subsets(string))
``````

In the above example, the code defines a `get_subsets` function that generates all possible subsets (power set) of a given set. The implementation uses list comprehensions and bitwise operations to create the subsets.

In this method, we start with defining a function named `get_subsets` that takes a set (`fullset`) as input.

The `listrep = list(fullset)` code converts the input set to a list (`listrep`). This is done to allow indexing and iteration.

Next, `n = len(listrep)` determines the length of the list (number of elements in the set).

For the list comprehension for the generation of subset, `return [[listrep[k] for k in range(n) if i & 1 << k] for i in range(2 ** n)]`, the outer list comprehension generates a list of subsets.

Then, the inner list comprehension generates each subset by iterating over the indices of the original set and including elements where the corresponding bit in the binary representation of `i` is set.

The outer loop runs for all possible values of `i` from `0` to `2^n - 1`, generating all possible subsets.

Lastly, we call the `get_subsets` function with the example set in the code, `print(get_subsets(string))`, to print the result.

Output:

``````[[], ['x'], ['y'], ['x', 'y'], ['z'], ['x', 'z'], ['y', 'z'], ['x', 'y', 'z']]
``````

The above code example outputs all possible subsets of the set `["x", "y", "z"]` as seen in the given code output.

## Use the Recursive Method to Find a Power Set in Python

The recursive method is a method where a function keeps on invoking itself with different arguments. This method can be implemented in a function in Python to find the power set of a set.

For example,

``````def powerSet(string, index, c):
if index == len(string):
print(c)
return
powerSet(string, index + 1, c + string[index])
powerSet(string, index + 1, c)

s1 = ["a", "b", "c"]
index = 0
c = ""
powerSet(s1, index, c)
``````

The code above implements a recursive method to generate the power set of a given set. The function `powerSet` takes three parameters: `string` (the set), `index` (the current index being considered), and `c` (the current subset being formed).

The `if index == len(string):` line checks if the current index is equal to the length of the set. If true, it means we have reached the end of the set, and the current subset (`c`) is printed.

Then, `powerSet(string, index + 1, c + string[index])` calls the `powerSet` function recursively, including the current element at the index in the subset (`c`). Next, `powerSet(string, index + 1, c)` calls the `powerSet` function recursively without including the current element at the index in the subset (`c`).

Lastly, `powerSet(s1, index, c)` calls the `powerSet` function with the example set and initial parameters, in which we initialized as `s1 = ["a", "b", "c"]`, `index = 0`, and `c = ""`.

Output:

``````abc
ab
ac
a
bc
b
c
``````

The code above outputs all possible subsets of the set `["a", "b", "c"]` using recursion.

## Conclusion

In this tutorial, we explored multiple methods for generating the power set of a set in Python.

We covered the iterative approach, leveraging nested loops and bitwise operations, providing a faster alternative to recursion. Additionally, we demonstrated the use of the `itertools.combinations` function and list comprehensions for concise power set generation.

Lastly, we also discussed the recursive method, showcasing how a function can invoke itself with different arguments to find the power set of a set.

Each method was accompanied by clear explanations and practical examples, offering a versatile set of tools for power set calculations across diverse scenarios.