Problem Statement

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: 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.

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

Topswops   is also known as   Fannkuch   from the German word   Pfannkuchen   meaning   pancake.

Let's start with the solution:

sub next_swop {
  my( $max, $level, $p, $d ) = @_;
  my $swopped = 0;
  for( 2..@$p ){ # find possibilities
    my @now = @$p;
    if( $_ == $now[$_-1] ) {
      splice @now, 0, 0, reverse splice @now, 0, $_;
      $swopped = 1;
      next_swop( $max, $level+1, \@now, [ @$d ] );
    }
  }
  for( 1..@$d ) { # create possibilities
    my @now = @$p;
    my $next = shift @$d;
    if( not $now[$next-1] ) {
      $now[$next-1] = $next;
      splice @now, 0, 0, reverse splice @now, 0, $next;
      $swopped = 1;
      next_swop( $max, $level+1, \@now, [ @$d ] );
    }
    push @$d, $next;
  }
  $$max = $level if !$swopped and $level > $$max;
}

sub topswops {
  my $n = shift;
  my @d = 2..$n;
  my @p = ( 1, (0) x ($n-1) );
  my $max = 0;
  next_swop( \$max, 0, \@p, \@d );
  return $max;
}

printf "Maximum swops for %2d cards: %2d\n", $_, topswops $_ for 1..10;