| 12 | |
| 13 | |
| 14 | def fannkuch(n): |
| 15 | count = list(range(1, n + 1)) |
| 16 | max_flips = 0 |
| 17 | m = n - 1 |
| 18 | r = n |
| 19 | perm1 = list(range(n)) |
| 20 | perm = list(range(n)) |
| 21 | perm1_ins = perm1.insert |
| 22 | perm1_pop = perm1.pop |
| 23 | |
| 24 | while 1: |
| 25 | while r != 1: |
| 26 | count[r - 1] = r |
| 27 | r -= 1 |
| 28 | |
| 29 | if perm1[0] != 0 and perm1[m] != m: |
| 30 | perm = perm1[:] |
| 31 | flips_count = 0 |
| 32 | k = perm[0] |
| 33 | while k: |
| 34 | perm[:k + 1] = perm[k::-1] |
| 35 | flips_count += 1 |
| 36 | k = perm[0] |
| 37 | |
| 38 | if flips_count > max_flips: |
| 39 | max_flips = flips_count |
| 40 | |
| 41 | while r != n: |
| 42 | perm1_ins(r, perm1_pop(0)) |
| 43 | count[r] -= 1 |
| 44 | if count[r] > 0: |
| 45 | break |
| 46 | r += 1 |
| 47 | else: |
| 48 | return max_flips |
| 49 | |
| 50 | |
| 51 | if __name__ == "__main__": |