ID : 484

viewed : 239

Tags : PythonPython Set

92

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.

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 `

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

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']] `

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 `