use strict;
use warnings;
use feature 'say';

use List::Util qw/ first shuffle max /;
use Compress::Zlib 'compress';
use POSIX 'ceil';

use constant ITEM => qr(< \d+ >);

my @input = fake_data( 555, 55 );
#say scalar @input;                  # 2096

my $low_mark  = gauge(( \@input ) x 100 );
my $high_mark = gauge( map [ shuffle @input ], 0 .. 99 );

my $supf_mark = gauge( map verify( supf( \@input )), 0 .. 99 );
my $mrcs_mark = gauge( map verify( mrcs( \@input )), 0 .. 99 );

printf "Looks like \"supf\" provides %.0f%% of possible entropy\n", 
    100 * ( $supf_mark - $low_mark ) / ( $high_mark - $low_mark );
printf "Looks like \"mrcs\" provides %.0f%% of possible entropy\n", 
    100 * ( $mrcs_mark - $low_mark ) / ( $high_mark - $low_mark );

sub gauge { length compress join '', map @$_, @_ }

sub verify {
    my $r = shift;
    my $s = join '', @$r;
    die if $s =~ /(ITEM)\1/;
    return $r
}

sub fake_data {
    my ( $uniq, $pivot ) = @_;

    my @tmp = map { sprintf '< %09d >', rand 1e9 } 0 ... $uniq;
    my @out;
    push @out, @tmp[ 0 .. $_ ] for 0 .. $pivot;
    @out = shuffle( @out, @tmp[ $pivot + 1 .. $uniq ]);

    return @out
}

sub supf {                      # shuffle/unshift/push/first
    my $input_ref = shift;

    my @in = shuffle @$input_ref;
    my @out = shift @in;

    LOOP:
    while( @in )
      {
      for my $in ( 0 .. $#in )
        {
        if( $in[$in] ne $out[0] ) # put at start
          {
          unshift @out, splice @in, $in, 1;
          next LOOP;
          }
        elsif( $in[$in] ne $out[-1] ) # put at end
          {
          push @out, splice @in, $in, 1;
          next LOOP;
          }
        else # put in first middle place it fits
          {
          if( my $pick = first {
            $out[$_ - 1] ne $in[$in] and $out[$_] ne $in[$in] } 1 .. $#out )
            {
            splice @out, $pick, 0, splice @in, $in, 1;
            next LOOP;
            }
          }
        }
      die "FAILED\nin\n @in\nout\n @out";
      }
    return \@out;
}

sub mrcs {                      # matrix rows/columns shuffle
    my $input_ref = shift;
    
    my %counts; $counts{ $_ } ++ for @$input_ref;
    
    my $nrows = max values %counts;
    my $ncols = ceil @$input_ref / $nrows;

    my @frequent_keys = grep { $counts{ $_ } == $nrows } keys %counts;
    delete @counts{ @frequent_keys };

    my @arranged = (( map {( $_ ) x $nrows } @frequent_keys ),
                    ( map {( $_ ) x $counts{ $_ }} keys %counts ));
    $#arranged = $nrows * $ncols - 1;

    my @matrix = map [ splice @arranged, 0, $nrows ], 0 .. $ncols - 1;

    my @row_perm = shuffle 1 .. $ncols - 1;     # exclude 0th column
    my @col_perm = shuffle 0 .. $nrows - 1;

    for my $col ( @matrix ) {
        splice @$col, 0, $nrows, @$col[ @col_perm ];
    }
    splice @matrix, 1, $ncols - 1, @matrix[ @row_perm ];

    my @ret = grep defined, map {       # transpose & flatten
        my $row_i = $_;
        map { $matrix[ $_ ][ $row_i ]} 0 .. $ncols - 1
    } 0 .. $nrows - 1;

    return \@ret;
}