How to Find Powerset in Python
 Use the Iterative Approach to Get a Power Set in Python

Use the
itertools.combinations
Function to Find a Power Set in Python  Use the List Comprehension Method to Find a Power Set in Python
 Use the Recursive Method to Find a Power Set in Python
 Conclusion
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.