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:

• Decision Tree Regression in Python using scikit learn