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   from the German word   Pfannkuchen   meaning   pancake.



Related tasks

   Number reversal game
   Sorting algorithms/Pancake sort


with javascript_semantics
function fannkuch(integer n)
    sequence count = tagset(n),
             perm1 = tagset(n)
    integer maxFlipsCount = 0, r = n+1
    while true do
        while r!=1 do
            count[r-1] = r
            r -= 1
        end while
        if not (perm1[1]=1 or perm1[n]=n) then
            sequence perm = perm1
            integer flipsCount = 0,
                    k = perm[1]
            while k!=1 do
                perm = reverse(perm[1..k]) & perm[k+1..n]
                flipsCount += 1
                k = perm[1]
            end while
            if flipsCount>maxFlipsCount then
                maxFlipsCount = flipsCount
            end if
        end if
        -- Use incremental change to generate another permutation
        while true do
            if r>n then return maxFlipsCount end if
            integer perm0 = perm1[1]
            perm1[1..r-1] = perm1[2..r] 
            perm1[r] = perm0
            count[r] -= 1
            if count[r]>1 then exit end if
            r += 1
        end while
    end while
end function -- fannkuch
 
atom t0 = time()
for i=1 to iff(platform()=JS?9:10) do
    ?fannkuch(i)
end for
?elapsed(time()-t0)
