[Tutor] recursion

[Alan Gauld]

On 05/02/16 02:03, noopy via Tutor wrote:

> I just cannot get my head around the following code, maybe someone could 
> explain it to me.

I'll try but it is a little bit tricky.

> def permutations(items):
>      n = len(items)
>      if n==0: yield []
>      else:

I assume this bit is clear enough?

>          for i in range(len(items)):
>              for cc in permutations(items[:i]+items[i+1:]):
>                  yield [items[i]]+cc

This bit is where the tricky stuff happens.
The key is in the slicing of items.
items[:i]+items[i+1:] effectively removes item[i] from the list.
So the 'for cc' line is saying:
  find the permutations of everything except item[i].
  then add items[i] to each of those permutations.
So for a single element it returns that element plus the empty list.

The recursion then repeats that for the reduced list.
So using XYZ as in your code:
for the first iteration of XYZ
   the first level calls for permutations of YZ and
   the second level calls for permutations of Z followed by Y
It then yields X plus those permutations - XYZ, XZY
for the second iteration of XYZ
   the first level calls for permutations of XZ and
   the second level calls for permutations of Z followed by X
It then yields Y plus those permutations - YXZ, YZX
for the third iteration of XYZ
   the first level calls for permutations of XY and
   the second level calls for permutations of X followed by Y
It then yields Z plus those permutations - ZXY, ZYX

I may have the return orders wrong because I didn't actually run it.
But that's the basic concept.

> for p in permutations(list("XYZ")):
>      print(''.join(p))

And this loop just joins the list back into strings.

> I have a problem with the following understanding:
> when I am in the recursion and call "for cc in permutations("Z")", the 
> next level of the recursion will do "for cc in permutations([])", which 
> will yield an empty list.

Yes, but the previous level then yields Z plus an empty list.

> So although "for cc in permutations("Z")" does have an item it does 
> "yield [items[i]]+cc" - thats the confusion for me. I hope I could 
> express myself clearly.

It is confusing. Maybe the easiest way to see it would be to
run it in a debugger with a break point set on the for cc
loop and look at items each time it stops.


-- 
Alan G
Author of the Learn to Program web site
http://www.alan-g.me.uk/
http://www.amazon.com/author/alan_gauld
Follow my photo-blog on Flickr at:
http://www.flickr.com/photos/alangauldphotos