CODEWITHSUNDEEP
pythonpython-3.xrecursionpowerset
blik3o
blik3o

Reputation: 41

Powerset recursive, list comprehension python3

I'm new to Python3 and are trying to do a recursive powerset function. It should use list comprehension.

I wrote:

def powerset(seq):
    if not seq:
       return [[]]
    return powerset(seq[1:]) + [[seq[0]] + n for n in powerset(seq[1:])]

This function works but I got feedback and was told it was unnecessary to call the function two times. It did to much computing. It should easily be able to compute up to 20 powersets. So how should I do? I can't get it to work without calling the function twice. Thanks.

Upvotes: 2

Views: 1351

Answers (1)

tobias_k
tobias_k

Reputation: 82899

Just calculate powerset(seq[1:]) once, store it in a variable, and use it twice:

def powerset(seq):
    if not seq:
        return [[]]
    ps = powerset(seq[1:])
    return ps + [[seq[0]] + n for n in ps]

The difference to yours is that this way, you use ps twice, but you compute it just once.

Alternatively, you could use a double list-comprehension (if you like that sort of thing...)

def powerset(seq):
    return [x for ps in powerset(seq[1:]) for x in ([seq[0]] + ps, ps)] if seq else [[]]

Here, the same temporary variable ps is defined inside the list comprehension. Note, however, that the results will be in a slightly different order this way.

I feel very unclear. I actually don't understand how just assigning it to a variable can change that? It means the same thing?

You seem to think too much in terms of pure math here. In programming, y = f(x) does not mean "y is the same as/synonymous for f(x)", but "assign the result of f(x) to y".

Upvotes: 1

Related Questions