use Time::HiRes qw( gettimeofday tv_interval );

for my $num(1..10){
my @start_time = gettimeofday();
print "Pfannkuchen($num) = ".fannkuch ($num)." for:\n";
print sort @max_sequence;
my @end_time = gettimeofday();
print tv_interval ( \@start_time, \@end_time )," elapsed seconds.\n\n";
};

sub fannkuch {
    my $n = shift;
    my @p;
    my @q;
    my $tmp;
    my $maxflips = 0;
    my $flips;

    for ($i=0; $i < $n; $i++) { $p[$i] = 1 + $i; }

  BRK: for (;;) {

    	if ($p[0] != 1) {

    	    @q = @p;

    	    for ($flips = 0; ($k = $q[0]) != 1; $flips++) {
    	    	for ($k--,$i=0; $i < $k; $i++, $k--) {
    	    	    $tmp = $q[$i];
    	    	    $q[$i] = $q[$k];
    	    	    $q[$k] = $tmp;
    	    	}
    	    }
    	    if ($flips > $maxflips) {
				$maxflips = $flips;
				@max_sequence = ();
			}
			push @max_sequence, join '', @p,"\n" if ($maxflips eq $flips);
    	}

    	$k = $j = 0;
    	for ($i=1; $i < $n; $i++) {
    	    $j = $i if ($p[$i-1] < $p[$i]);
    	    $k = $i if ($j && $p[$i] > $p[$j-1]);
    	}
    	last BRK if (!$j);

    	$tmp = $p[$j-1];
    	$p[$j-1] = $p[$k];
    	$p[$k] = $tmp;

    	for ($i=$j,$j=$n-1; $i < $j; $i++, $j--) {
    	    $tmp = $p[$j];
    	    $p[$j] = $p[$i];
    	    $p[$i] = $tmp;
    	}
    }

    return $maxflips;
}