*Given a starting permutation of 1..n items, consider the leftmost value and call it L:*

*If L is not 1 then reverse the leftmost L values in the sequence.**Repeat, counting the number of reversions required until L becomes 1*

*Repeat the process for all permutations of 1..n items and report the maximum number of reversions required amongst all the permutations.*

I initially came up with this doodle:

>>> def f1(p): i = 0 while p[0] != 1: i += 1 print(i,p) p[:p[0]] = p[:p[0]][::-1] return i >>> f1([4,2,1,5,3]) 1 [4, 2, 1, 5, 3] 2 [5, 1, 2, 4, 3] 3 [3, 4, 2, 1, 5] 4 [2, 4, 3, 1, 5] 5 [4, 2, 3, 1, 5] 5 >>> def f1(p): i = 0 while p[0] != 1: i += 1 #print(i,p) p[:p[0]] = p[:p[0]][::-1] return i >>> f1([4,2,1,5,3]) 5 >>> from itertools import permutations >>> def fannkuch(n): return max(f1(list(p)) for p in permutations(range(1, n+1))) >>> for n in range(1, 11): print(n,fannkuch(n)) 1 0 2 1 3 2 4 4 5 7 6 10 7 16 8 22 9 30 10 38 >>>

### Range

Python usually uses ranges 0..n-1 so I made that modification:>>> def f1(p): i = 0 while p[0]: i += 1 p[:p[0] + 1] = p[:p[0] + 1][::-1] return i >>> def fannkuch(n): return max(f1(list(p)) for p in permutations(range(n)))

### Speed

I had to wait for fannkuch(10) so decided to do some quick optimization and created name p0 to mop up some array lookups:>>> def f1(p): i, p0 = 0, p[0] while p0: i += 1 p0 += 1 p[:p0] = p[:p0][::-1] p0 = p[0] return i

## Those assignments

It was at this stage that I thought*"Ooh, I haven't used that new assignment in Python 3 where you can use *name on the left hand side of an assignment",*plus, I could add it in to an already complex assignment just for the hell of it.

I am creating p, so I should be able to assign p[0] to p0 and discard p[1:] for the purposes of the assignment into *_. I tried:

>>> def f1(p): i, p0 = 0, p[0] while p0: i += 1 p0 += 1 p0, *_ = p[:p0] = p[:p0][::-1] return i >>> for n in range(1, 11): print(n,fannkuch(n)) 1 0 2 1 3 2 Traceback (most recent call last): File "" , line 1, infor n in range(1, 11): print(n,fannkuch(n)) File " " , line 2, in fannkuch return max(f1(list(p)) for p in permutations(range(n))) File "" , line 2, inreturn max(f1(list(p)) for p in permutations(range(n))) File " " , line 6, in f1 p0, *_ = p[:p0] = p[:p0][::-1] KeyboardInterrupt >>>

I had to interrupt it as it failed to return.

**Something was wrong!**

I thought it might be the order of assignment and tried:

>>> def f1(p): i, p0 = 0, p[0] while p0: i += 1 p0 += 1 p[:p0] = p0, *_ = p[:p0][::-1] return i >>> for n in range(1, 11): print(n,fannkuch(n)) 1 0 2 1 3 2 4 4 5 7 6 10 7 16 8 22 9 30 10 38 >>>

Yay Success!!

But I did this so you

*don't*have to :-)

It is a few optimizations too far, and, when you look in the docs they state:

"

WARNING: Although the definition of assignment implies that overlaps between the left-hand side and the right-hand side are ‘safe’ (for example

`a, b= b, a`swaps two variables), overlaps

*within*the collection of assigned-to variables are not safe! For instance, the following program prints

`[0, 2]`:

## No comments:

## Post a Comment