CODEWITHSUNDEEP
pythonscalarecursion
Adrienne
Adrienne

Reputation: 2680

Why doesn't this Python code for powerset work?

I can't identify anything blatantly wrong with it except that I am trying to do Scala-type operations with Python.

def powerset(arr):
        if len(arr) == 0:
            return []
        elif len(arr) > 1:
            return powerset(arr[1:])+[arr[0]]

I consistently get a error:

return powerset(arr[1:])+[arr[0]]

TypeError: unsupported operand type(s) for +: 'NoneType' and 'list'

Upvotes: 0

Views: 116

Answers (2)

Joran Beasley
Joran Beasley

Reputation: 113950

if len(arr) == 1

nothing is returned ...

just change it to 

def powerset(arr):
    if len(arr)>0:
         return powerset(arr[1:])+[arr[0]]
    else:
         return []

here is a powerset function from https://docs.python.org/2/library/itertools.html

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))

here is a powerset implementation that uses slightly less magic

def powerset(seq):
    """
    Returns all the subsets of this set. This is a generator.
    """
    if len(seq) <= 1:
        yield seq
        yield []
    else:
        for item in powerset(seq[1:]):
            yield [seq[0]]+item
            yield item

print list(powerset([1,2]))

Upvotes: 4

Prune
Prune

Reputation: 77837

If arr has only one element, you don't return anything. This becomes None. Your next-to-last iteration blows up because powerset() is None.

Change one line:

elif len(arr) > 1:

... becomes ...

else:

Upvotes: 1

Related Questions