CODEWITHSUNDEEP
python
Dung Lemanh
Dung Lemanh

Reputation: 84

I am stuck with recursion in Power Set using Python

I am writing a program to return a set of subset of number. For example: list = [1,2,3] my desired function will return [[], [1], [2], [2,1], [3], [3,1], [3,2], [3,2,1]] However, it returns [[], [1], [2], [3]] Here is my code

# Write a powerSet function
def powerSet(list):
    if len(list) == 0:
        return [[]];
    else:
        temp = list.pop()
    return powerSet(list) + [[temp] + x for x in powerSet(list)];

list = [1,2,3];
print(powerSet(list));

Upvotes: 1

Views: 843

Answers (2)

Zealseeker
Zealseeker

Reputation: 823

There is a built-in package for "subset"

import itertools

def subset(x):
    all_list = []
    for i in range(len(x)+1):
        all_list+=list(itertools.combinations(x,i))
    return all_list

print subset([1,2,3])
[output>>>] [(), (1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]

Upvotes: 1

hsfzxjy
hsfzxjy

Reputation: 1322

The problem is that you mutate the list object, so the two powerSet in the last line will not receive the same list (for example, in the first call, the first powerSet will get [1,2] but the second one will get [1]).

The solution is to copy the list when passing it down:

powerSet(list[:]) + [[temp] + x for x in powerSet(list[:])]

Upvotes: 2

Related Questions