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


 
(subscriptrange):
topswap: procedure options (main); /* 12 November 2013 */
   declare cards(*) fixed (2) controlled, t fixed (2);
   declare dealt(*) bit(1) controlled;
   declare (count, i, m, n, c1, c2) fixed binary;
   declare random builtin;
 
   do n = 1 to 10;
      allocate cards(n), dealt(n);
      /* Take the n cards, in order ... */
      do i = 1 to n; cards(i) = i; end;
      /* ... and shuffle them. */
      do i = 1 to n;
         c1 = random*n+1; c2 = random*n+1;
         t = cards(c1); cards(c1) = cards(c2); cards(c2) = t;
      end;
      /* If '1' is the first card, game is trivial; swap it with another. */
      if cards(1) = 1 & n > 1 then
         do; t = cards(1); cards(1) = cards(2); cards(2) = t; end;
 
      count = 0;
      do until (cards(1) = 1);
         /* take the value of the first card, M, and reverse the first M cards. */
         m = cards(1);
         do i = 1 to m/2;
            t = cards(i); cards(i) = cards(m-i+1); cards(m-i+1) = t;
         end;
         count = count + 1;
      end;
      put skip edit (n, ':', count) (f(2), a, f(4));
   end;
end topswap;
 