Scamming the Coding Interview: Problem #1: Generate Power Set

generate_power_set.py

"""
Scamming the Coding Interview
"""


def generate_super_sets(power_set, elements, running_set, start_index):

    if start_index > len(elements):
        return

    for i, num in enumerate(elements):

        if i < start_index:
            continue

        temp_running_set = running_set[:]

        temp_running_set.append(num)

        power_set.append(temp_running_set)

        generate_super_sets(power_set, elements, temp_running_set, i+1)


if __name__ == '__main__':

    power_set = []
    elements = [1, 2, 3]
    power_set.append([])
    generate_super_sets(
        power_set=power_set, elements=elements, running_set=[], start_index=0
    )

    print(power_set)

Just big no to recursion - you do not need it.

given the size of your set is n you know size of power set is m=2**n. You can generate each subset based on binary encoding:

def mask(number):
    while number:
        bit, number = number % 2, number // 2
        yield bit


def supersets(s):
    l = list(s)
    subsets = 2 ** len(s)
    for subset_no in range(subsets):
        yield {element for element, include in zip(l, mask(subset_no)) if include }

so if your set is {1,3,'k'} - you will have 2**3 subsets

[set(), {1}, {'k'}, {1, 'k'}, {3}, {1, 3}, {'k', 3}, {1, 'k', 3}]

If it's magic for you the mask generator is changin number to it's binary representation:

list(mask(0)) == []
list(mask(1)) == [1]
list(mask(2)) == [0, 1]  
list(mask(3)) == [1, 1]
list(mask(4)) == [0, 0, 1]
list(mask(5))) == [1, 0, 1]
....

having that mask you can zip it with the orginal set and filter by it value to generate final subset