# Untitled

a guest
Feb 16th, 2012
125
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #!perl -w
2. # Chris Dolan, chris@chrisdolan.net
3. # Code challenge: http://beust.com/weblog/2012/02/16/a-new-coding-challenge-2/
4. use strict;
5.
6. # Syntax:
7. #    \$0 <num>     (outputs a shuffled list of 0..<num>-1)
8. #    \$0 -t <num>  (tests randomness of shuffled list of 0..<num>-1)
9.
10. # Short version:
11. # perl -le'@a=0..\$ARGV[0]-1;print splice @a, rand(@a), 1 while @a' 5
12.
13. sub shuffle {
14.    my (\$n) = @_;
15.    my @in = 0..\$n-1;
16.    my @out;
17.    while (@in) {
18.       push @out, splice @in, rand(@in), 1;
19.    }
20.    return @out;
21. }
22.
23. sub test {
24.    my (\$n, \$iter) = @_;
25.
26.    # N x N array counting how many times number i appears in position j
27.    my @counts = map {[]} 0 .. \$n-1;
28.    for (my \$k=0; \$k<\$iter; ++\$k) {
29.       my @o = shuffle(\$n);
30.       for (my \$j=0; \$j<\$n; ++\$j) {
31.          \$counts[\$o[\$j]][\$j]++;
32.       }
33.    }
34.
35.    print "number x position\n";
36.    for (my \$j=0; \$j<\$n; ++\$j) {
37.       print "@{\$counts[\$j]}\n";
38.    }
39.    print "\n";
40.
41.    print "deviation from mean (", \$iter/\$n, ")\n";
42.    for (my \$j=0; \$j<\$n; ++\$j) {
43.       my @dev = map { \$_ - \$iter/\$n } @{\$counts[\$j]};
44.       print "@dev\n";
45.    }
46.    print "\n";
47.
48.    my \$sumsq = 0;
49.    for (my \$j=0; \$j<\$n; ++\$j) {
50.       for (my \$i=0; \$i<\$n; ++\$i) {
51.          \$sumsq += (\$counts[\$j][\$i] - \$iter/\$n)**2;
52.       }
53.    }
54.    print "std dev = ", sqrt(\$sumsq/(\$iter-1)), "\n";
55. }
56.
57. my \$n = shift;
58. if (\$n eq '-t') {
59.    \$n = shift;
60.    test(\$n, 1_000_000);
61. } else {
62.    my @o = shuffle(\$n);
63.    print "@o\n";
64. }
RAW Paste Data