Python program to get all subsets of set using Loops and Functions
The topic mainly deals with the concept of generating subsets of a given set.
This is important because, later on in advanced programming, it is helpful in implementing Dynamic Programming Solutions.
Python program to generate all possible subsets of a given set within a list
Moreover, a subset is defined as a part of a set or the whole set itself.
Let’s understand the concept with some examples and then implement it.
Example 1:
Input : [1, 2]
Output : [[], [1], [1, 2], [2]]
Example 2:
Input :[1, 2, 3]
Output :[[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]
Explanation of the Solution :
This program solution is described in many different ways Recursion, slicing, Itertools in python.
But this solution is based on simple loops and functions.
We know there are (2^n) subsets for a set of n elements.
Moreover, this solution is based on a simple idea :
Convert the numbers 0 to (2^n-1) into binary numbers, where n is the length of list
Now represent the binary equivalents in (n number of bits)
ex: a=[1, 2, 3, 4], n=4
0: (0) : (0000)
1: (1) : (0001)
7: (111) : (0111) and so on
Certainly, there is now a Binary list of elements represented in n bits.
Now traverse every digit in the sub list and append those values which are 1 and exclude those which are 0.
Let’s jump on to code what we have learned above,
def decimalToBinary(n): # converting decimal to binary b = 0 i = 1 while (n != 0): r = n % 2 b+= r * i n//= 2 i = i * 10 return b def makeList(k): # list of the binary element produced a =[] if(k == 0): a.append(0) while (k>0): a.append(k % 10) k//= 10 a.reverse() return a def checkBinary(bin, l): temp =[] for i in range(len(bin)): if(bin[i]== 1): temp.append(l[i]) return temp l =[1, 2, 3] binlist =[] subsets =[] n = len(l) for i in range(2**n): s = decimalToBinary(i) arr = makeList(s) binlist.append(arr) for i in binlist: k = 0 while(len(i)!= n): i.insert(k, 0) # representing the binary equivalent according to len(l) k = k + 1 for i in binlist: subsets.append(checkBinary(i, l)) # print(binlist) print this for more understanding print(subsets)
Output : [[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]
This is how the subsets can be produced using basic loops and functions in Python.
I hope this is pretty much clear to implement the concept regarding subsets.
Also read:
Leave a Reply