CODEWITHSUNDEEP
pythonrecursion
limitless
limitless

Reputation: 669

Trying to build the power set function

I'm trying to build power set function. When i build it as a generator it work fine.

But i want to write it as a regular function 

def power_set(group):
    if len(group)==0:
        return set()
    else:
        last=group.pop()
        for sub in power_set(group):
            return (sub|{last})
            return (sub)

Anyone know what the problem could be ?

Upvotes: 0

Views: 97

Answers (2)

JonathanZ
JonathanZ

Reputation: 1086

You can be lazy and just create a list that contains all the items produced by your generator version

powSet = list( power_set_generator(group) )

assuming power_set_generator() is your generator version that's working okay.

Upvotes: 0

glibdud
glibdud

Reputation: 7840

You're trying to turn a generator into a function by trivially changing all yields to returns. That will almost never work, as it completely changes the flow. A generator function will continue after a yield, but a return returns permanently.

In your case, you start by passing a large set into the power_set() function. It will happily recurse, with one less item each time, until it hits a single item. At that point the pop() statement will remove the last item, and it will then call power_set() with an empty set as input. This will return immediately as an empty set, causing the for loop to evaluate to:

for sub in set():

Since this is empty, it will skip the body of the for loop (the two returns) and reach the end of the function, thus by definition returning None. This causes your recursion stack to unroll one more level and try to execute:

for sub in None:

And that's the cause of the exception you're getting.

To fix it, you can't return one value at a time, but must return all values for a particular invocation of power_set() at once.

def power_set(group):
    if len(group)==0:
        return [set()]
    else:
        last=group.pop()
        s = []
        for sub in power_set(group):
            s.append(sub|{last})
            s.append(sub)
        return s

Upvotes: 1

Related Questions