#!perl -w
# Chris Dolan, chris@chrisdolan.net
# Code challenge: http://beust.com/weblog/2012/02/16/a-new-coding-challenge-2/
use strict;

# Syntax:
#    $0 <num>     (outputs a shuffled list of 0..<num>-1)
#    $0 -t <num>  (tests randomness of shuffled list of 0..<num>-1)

# Short version:
# perl -le'@a=0..$ARGV[0]-1;print splice @a, rand(@a), 1 while @a' 5

sub shuffle {
   my ($n) = @_;
   my @in = 0..$n-1;
   my @out;
   while (@in) {
      push @out, splice @in, rand(@in), 1;
   }
   return @out;
}

sub test {
   my ($n, $iter) = @_;

   # N x N array counting how many times number i appears in position j
   my @counts = map {[]} 0 .. $n-1;
   for (my $k=0; $k<$iter; ++$k) {
      my @o = shuffle($n);
      for (my $j=0; $j<$n; ++$j) {
         $counts[$o[$j]][$j]++;
      }
   }

   print "number x position\n";
   for (my $j=0; $j<$n; ++$j) {
      print "@{$counts[$j]}\n";
   }
   print "\n";

   print "deviation from mean (", $iter/$n, ")\n";
   for (my $j=0; $j<$n; ++$j) {
      my @dev = map { $_ - $iter/$n } @{$counts[$j]};
      print "@dev\n";
   }
   print "\n";

   my $sumsq = 0;
   for (my $j=0; $j<$n; ++$j) {
      for (my $i=0; $i<$n; ++$i) {
         $sumsq += ($counts[$j][$i] - $iter/$n)**2;
      }
   }
   print "std dev = ", sqrt($sumsq/($iter-1)), "\n";
}

my $n = shift;
if ($n eq '-t') {
   $n = shift;
   test($n, 1_000_000);
} else {
   my @o = shuffle($n);
   print "@o\n";
}