Find Powerset in Python

  1. Use the Iterative Approach to Get a Powerset in Python
  2. Use the itertools.combinations Function to Find a Powerset in Python
  3. Use the List Comprehension Method to Find a Powerset in Python
  4. Use the Recursive Method to Find a Powerset in Python

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 is also known as a powerset. There can be a power set of lists, sets, strings, etc., in Python.

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

Use the Iterative Approach to Get a Powerset in Python

Though we can use both recursive approach and iterative approach to find a powerset, the iterative approach is preferred over recursive as it a faster process.

We use a nested for loop to create such a powerset.

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

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

Use the itertools.combinations Function to Find a Powerset in Python

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 for-loop.

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

See the code below.

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)

Output:

x
y
z
xy
xz
yz
xyz

Use the List Comprehension Method to Find a Powerset 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 use a nested for loop in this method also.

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

Output:

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

Use the Recursive Method to Find a Powerset in Python

The recursive method is a method where a function keeps on invoking itself with different arguments. We can create a recursive function to find the powerset 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)

Output:

abc
ab
ac
a
bc
b
c
Contribute
DelftStack is a collective effort contributed by software geeks like you. If you like the article and would like to contribute to DelftStack by writing paid articles, you can check the write for us page.

Related Article - Python Set

  • Create Ordered Set in Python
  • Join Two Sets in Python