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


go ?=>
  member(N,1..10),
  Perm = 1..N,
  Rev = Perm.reverse(),
  Max = 0,
  while(Perm != Rev)
    next_permutation(Perm),
    C = topswops(Perm),
    if C > Max then
       Max := C
    end
  end,
  printf("%2d: %2d\n",N,Max),
  fail,  
  nl.
go => true.
 
topswops([]) = 0 => true.
topswops([1]) = 0 => true.
topswops([1|_]) = 0 => true.
topswops(P) = Count =>  
   Len = P.length,
   Count = 0,
   while (P[1] > 1)
      Pos = P[1],
      P := [P[I] : I in 1..Pos].reverse() ++ [P[I] : I in Pos+1..Len],
      Count := Count + 1 
   end.
 
% Inline
next_permutation(Perm) =>
   N = Perm.length,
   K = N - 1,
   while (Perm[K] > Perm[K+1], K >= 0) 
      K := K - 1
   end,
   if K > 0 then
      J = N,
      while (Perm[K] > Perm[J])  J := J - 1 end,      
      Tmp := Perm[K],
      Perm[K] := Perm[J],
      Perm[J] := Tmp,
      R = N, 
      S = K + 1,
      while (R > S) 
         Tmp := Perm[R],
         Perm[R] := Perm[S],
         Perm[S] := Tmp,
         R := R - 1, 
         S := S + 1
      end
   end.