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
_______________________________________________
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor
