CODEWITHSUNDEEP
pythonrecursionnested-lists
liqiudilk
liqiudilk

Reputation: 181

Recursive Python function returning PowerSet of items

I'm trying to debug a program and am running into issues. Can anybody direct me to the issue here?

The program is meant to take a list of items, and returns the list of powersets for those items.

An example:

>>> getAllSubsets([1,2])
[[1,2],[1],[2],[]]

The code:

def getAllSubsets(lst):
    if not lst:
        return []
    withFirst = [ [lst[0]] + rest for rest in getAllSubsets(lst[1:]) ]
    withoutFirst = getAllSubsets(lst[1:])
    return withFirst + withoutFirst

Upvotes: 1

Views: 5728

Answers (3)

özgür Qzr
özgür Qzr

Reputation: 1

I found this solution on the internet:

def powset3(seq):
    if seq:
        p = powset3(seq[1:])
        return p + [x + seq[:1] for x in p]
    else:
        return [[]]

Upvotes: -1

spalac24
spalac24

Reputation: 1116

There are better recipes, yes. But I think the problem with your code is that you should replace return [] with return [[]]. The empty set is itself a subset.

Upvotes: 3

Cyphase
Cyphase

Reputation: 12022

There's a powerset generator in the recipes section of the itertools documentation; you should use that.

def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

Upvotes: 2

Related Questions