Topswops

Topswops is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Topswops is a card game created by John Conway in the 1970's.

Assume you have a particular permutation of a set of n cards numbered 1..n on both of their faces, for example the arrangement of four cards given by [2, 4, 1, 3] where the leftmost card is on top. A round is composed of reversing the first m cards where m is the value of the topmost card. rounds are repeated until the topmost card is the number 1 and the number of swaps is recorded. For our example the swaps produce:

    [2, 4, 1, 3]    # Initial shuffle
    [4, 2, 1, 3]
    [3, 1, 2, 4]
    [2, 1, 3, 4]
    [1, 2, 3, 4]

For a total of four swaps from the initial ordering to produce the terminating case where 1 is on top.

For a particular number n of cards, topswops(n) is the maximum swaps needed for any starting permutation of the n cards.

Task

The task is to generate and show here a table of n vs topswops(n) for n in the range 1..10 inclusive.

Note

Topswops is also known as Fannkuch.

Python

<lang python>>>> from itertools import permutations >>> def f1(p): i, p0 = 0, p[0] while p0: i += 1 p0 += 1 p[:p0] = p[:p0][::-1] p0 = p[0] return i

>>> def fannkuch(n): return max(f1(list(p)) for p in permutations(range(n)))

>>> 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 >>> </lang>