Python Forum

Hi,
I have started learning Python a week ago (I have previous experience with C++ and Java) and stumbled over piece of code I have trouble to understand. 

def power_set(l):
   if not l: 
      return [[]]
   return power_set(l[1:]) + [[l[0]] + x for x in power_set(l[1:])]

The code calculates the power set. For power_set({1,2,3,4}) the output is {{}, {1}, {2}, {1,2}, {3}, {1,3}, {2,3}, {1,2,3}, {4}, {1,4}, {2,4}, {1,2,4}, {3,4}, {1,3,4}, {2,3,4}, {1,2,3,4}}. While the if statement is clear, the last is not .

I would be thankful if someone could explain me the last line.

So, nasty recursive code with part of it wrapped in a list comp... wonderful.

Let's try breaking that line up:

power_set(l[1:]) + [[l[0]] + x for x in power_set(l[1:])]

We have:

power_set(l[1:])

and

[[l[0]] + x for x in power_set(l[1:])]

The first part is easy.  power_set(l[1:]) is the powerset of the current sequence without the first entry.
So if you ask for the power set of [1,2,3,4] it gives the power set of [2,3,4].

The second part is the first character in the sequence + the previous expression.
So if you ask for the powerset of [1,2,3,4] it gives you [1] + each set in the powerset of [2,3,4].


So to try once again to put this into words:
""" The powerset of any sequence is equal to (the powerset of the sequence without the first entry) + (the first entry +  (each set in the powerset of the sequence without the first entry))."""

Not sure if that is any clearer.  I tried. =P

Thank you very much. I have understood it now.
 
And yeah, it's the kind of recursive methods I wouldn't write myself voluntarily because of the hardness to read it (especially month later).

sometimes, code like that can earn you elegance points from the Ph.D people ... even if the code is wrong.