#!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";
}