Generates the power set of the set without using pre-defined library?-CodePudding

I am trying to generate the power set of the list,without using any library. For example, given the set {1, 2, 3}, it should return {{}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}

Note: We can use list also for it.

I have implemented the code , but it is not dynamic , it is for the specific length . How can I make it dynamic.

Code:

my_list = [0, 1, 2, 3]

first_list = []
second_list = [[]]
final_list = []

for iterate in my_list:
    second_list.append([iterate])
    
for outer_loop in my_list:
    for inner_loop in my_list:
        if outer_loop!=inner_loop:
            first_list.append([outer_loop, inner_loop])
            
result = (second_list   first_list)

for iterated in result:
    if sorted(iterated) not in final_list:
        final_list.append(iterated)
final_list   [my_list]

CodePudding user response：

Try this:

def get_powerset(s):
    x = len(s)
    subsets = []
    for i in range(1 << x):
        subsets.append([s[j] for j in range(x) if (i & (1 << j))])

    return subsets

lists = [[1, 2, 3], [0, 1, 2, 3]]
for num_list in lists:
    print(get_powerset(num_list))

Output:

[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
[[], [0], [1], [0, 1], [2], [0, 2], [1, 2], [0, 1, 2], [3], [0, 3], [1, 3], [0, 1, 3], [2, 3], [0, 2, 3], [1, 2, 3], [0, 1, 2, 3]]

CodePudding user response：

In addition to @Sabil's answer, a recursive approach:

def get_powerset(s):
    if len(s) == 0: 
        return []
    if len(s) == 1: 
        return [s] 
    without_s0 = get_powerset(s[1:])
    with_s0 = [subs   [s[0]] for subs in without_s0]
    return with_s0   without_s0

This solution assumes a item method, but that can be easily relaxed.

CodePudding user response：

You can use bin and access to element list like below:

>>> def pow_set(lst):
...    out = []
...    for idx in range(2**len(lst)):
...        out.append([b for a,b in zip(reversed(bin(idx)[2:]), lst) if a=='1'])
...    return out

>>> lst = [1,2,3]
>>> pow_set(lst)
[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
# for example 7 -> 0b111 -> then we access to lst in index 0,1,2
# for example 5 -> 0b101 -> then zip('101',123) -> [('1',1), ('0',2), ('1',3)] -> then we get elements if we have '1' -> [1,3]