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