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;
}

##</code><code>##

use warnings;
use strict;
use Time::HiRes qw( gettimeofday tv_interval );

my $maxflips = 0;
my @max_sequence;

for my $num ( 1 .. 10 ) {
    my @start_time = gettimeofday();
    @max_sequence = ();
    print "Pfannkuchen($num) = " . fannkuch( [ 1 .. $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 ( $aref, $level ) = ( @_, 0 );
    my ( $index, $copy, $ok ) = ( $level, [@$aref], $level + 1 == @$aref );
    do {
        if ($ok) {
            if ( $copy->[0] != 1 and $copy->[-1] != @$copy ) {
                my @q = @$copy;
#                my ( $i, $k, $flips );
                my ( $k, $flips );
                for ( $flips = 0 ; ( $k = $q[0] ) != 1 ; $flips++ ) {
#                    for ( $k--, $i = 0 ; $i < $k ; $i++, $k-- ) {
#                       @q[ $i, $k ] = @q[ $k, $i ];
#                    }
                    @q[ 0 .. $k-1 ] = reverse @q[ 0 .. $k-1 ];
                }
                if ( $flips > $maxflips ) {
                    $maxflips     = $flips;
                    @max_sequence = ();
                }
                push @max_sequence, join '', @$copy, "\n"
                  if ( $maxflips == $flips );
            }
        }
        else {
            fannkuch( $copy, 1 + $level );
        }
        @$copy[ $index - 1, $index ] = @$copy[ $index, $index - 1 ]
          if $index != 0;

    } while $index-- > 0;
    return $maxflips;
}