Power Set

PowerSet.py

#   /////////////////////////////////////////////////
#  --------------- Poer Set -----------------------
# ////////////////////////////////////////////////

'''
Logic : 

    Suppose we are given 'abc'
    Now take an temp array 

    [['a'] , ['b'] , ['c']] # temp array

    Also take a result power set array, and initialize it to 
    
    ['' , 'a' , 'b' , 'c']   # resultant power set

    Now we will start will 'a' (given string's 1st element)

    As first element of temp array is also 'a' and
    also 'aa' is not part of power set so we will skip this

    Now index 1 of temp is b now we will concatenate 'a' and 'b'
    and append it into index 1 as well as into our result. So

      [['a'] , ['b','ab'] , ['c']] # temp array
      ['' , 'a' , 'b' , 'c', 'ab']   # resultant power set

    index 2 is 'c' again concatenate and append in index 2 list and result

      [['a'] , ['b','ab'] , ['c','ac']] # temp array
      ['' , 'a' , 'b' , 'c', 'ab' , 'ac']   # resultant power set

    Now we will take second character of given string i.e. 'b'

    At index 0 of temp we have 'a' which is not equal 'b',
    but if we concatenate 'ba' then it will create a duplicate value in our power set
    So we will skip this index

    At index 1 of temp we have 'b' and 'ab' we can not also concatenate 'b' here
    So skip

    At index 2 of temp we have 'c' and 'ac' , here we can concatenate 'b'
    So our temp and result become

      [['a'] , ['b','ab'] , ['c','ac','cb'acb]] # temp array
      ['' , 'a' , 'b' , 'c', 'ab' , 'ac', 'cb' , 'acb']   # resultant power set

    By here we got all elements of powerset.

    result = ['' , 'a' , 'b' , 'c', 'ab' , 'ac', 'cb' , 'acb']


    Complexity : O(t*t*2^t) where t = n - 1

'''

def powerset(array):
    temp = [[x] for x in array]
    result = [''] + [x for x in array]
    for i in range(len(array)-1):                   # it runs (n-1) times in worst case
        for j in range(i+1,len(array)):             # it runs (n-1) times in worst case
            for k in range(len(temp[j])):           # it runs 2^(n-1) times in worst case
                x = temp[j][k] + array[i]
                result.append(x)
                temp[j].append(x)
    return result

print(powerset(list(str('abcd'))))  


'''
    Logic : 
        suppose we have given 'abc'
        Take a new array result and initialize it to ['']

        Now take first element of given string i.e. 'a'
        and concatenate it with all elements of result , and append in result
        So result become

            ['' , 'a']
                  ----
        Now take 'b'  and do same

            ['' , 'a' , 'b' , 'ab']
                        ----------
        now take 'c' and do same

            ['' , 'a' , 'b' , 'ab', 'c' , 'ac' , 'bc' , 'abc' ] # that's ot result
                                    -------------------------
        Basically here we are just adding a new item 
        into each combinations we found in previous step 

        Complexity : O(n2^n)

'''

def powerset1(array):
    power = ['']
    for i in array:                             # it runs n times in worst case
        for j in range(len(power)):             # it runs 2^n times in worst case
            power.append(power[j] + i)
    return power

print(powerset1('abcd'))

'''
Logic :

    Suppose we are given 'abc'

    We know size of a power set is 2 ^ n
    where n is no. of distinct characters

    So, what we do is

    c | b | a
    ---------------------------
    0 | 0 | 0  ---------------->  ''
    0 | 0 | 1  ---------------->  a         # here 1 is only in place of a
    0 | 1 | 0  ---------------->  b         # here 1 is only is place of b
    0 | 1 | 1  ---------------->  ab        # here 1 is in place of a and b
    1 | 0 | 0  ---------------->  c
    1 | 0 | 1  ---------------->  ac
    1 | 1 | 0  ---------------->  bc
    1 | 1 | 1  ---------------->  abc

    where ever we encounter 1 we add it to final element

    Process:
        let us take 2 variable

        x will go from (0 to 2^(length of given array)-1) i.e. (0,7)
        y will vary from (0, length of given array -1) i.e. (0,2)

        Initially: x = 0
                   y = 0
        For this case we will not get anything because AND of 0 to anything is 0

        Now : x = 1
              y = 0
        Bitwise AND x and (1 << y). Which means left shift 1 by y 
            So, for x = 0 we get '' ///////////////

        places i.e. 0 places and AND it with x

                So  x      = 001     # in bit format
                    1 << 0 = 001     # in bit format
                    AND = 001 -----------------------------> from here we get 'a'

            Now y = 1
                So  x      = 001     # in bit format
                    1 << 1 = 010     # in bit format
                   AND = 000 ----------------------------->     Nothing is appended to 'a'
            
            Now y = 2
                So  x      = 001     # in bit format
                    1 << 2 = 100     # in bit format
                   AND = 000 ----------------------------->      Nothing is appended to 'a'
            
            So, for x = 1 we get 'a' //////////////////////////

        FOr x = 2 Similar process
            So, for x = 2 we will get 'b'  //////////////////////

        For x = 3
            Now for y = 0:
                So  x      = 011     # in bit format
                    1 << 0 = 001     # in bit format
                    AND = 001 -----------------------------> from here we get 'a'

            Now for y = 1:
                So  x      = 011     # in bit format
                    1 << 1 = 010     # in bit format
                    AND = 001 -----------------------------> Append 'b' to 'a' , we get 'ab'
            
            Now for y = 2:
                So  x      = 011     # in bit format
                    1 << 2 = 100     # in bit format
                    AND = 001 -----------------------------> Nothing is appended to 'ab'
            
            So, for x = 3 we get 'ab' ///////////////////////////



        Similarly for other values of x
 

    Complexity : O(n2^n)

'''

def powerset2(array):
    power = []
    size_array = len(array)
    size_power = 2**size_array
    for i in range(size_power):                 # it runs 2^n times in worst case
        value = ''                              
        for j in range(size_array):             # it runs n times in worst case
            if (i & (1<<j) > 0):
                value += array[j]
        power.append(value)
    return power

print(powerset2('abcd'))