in reply to Re^6: Array problem
in thread Array problem

Oops, I was mistaken. I thought he was doing my $r = rand ($r);. I don't see any unfairness.

Replies are listed 'Best First'.
Re^8: Array problem
by BrowserUk (Patriarch) on Sep 29, 2008 at 04:25 UTC
    I don't see any unfairness.

    Okay, try running this and see if it changes your mind. 

    #! perl -slw
use strict;

our $N ||= 1e6;

my %stats;

my  @data = 'A' .. 'Z';

for my $n ( 1 .. $N ) {
    my @scratch = @data;

    foreach my $first ( @data ) {
        for my $j ( reverse $#scratch -2 .. $#scratch ) {
            my $r = rand( $j + 1 );
            @scratch[ $j, $r ] = @scratch[ $r, $j ];
            if( $scratch[ $j ] eq $first ) {
                my $r = rand $j;
                @scratch[ $j, $r ] = @scratch[ $r, $j ];
            }
        }
        ++$stats{ $_ } for @scratch[ -3 .. -1 ];
    }
    system 'cls'; printf "%8d\n", $n;
    printf "%s : %6d ( %+3d ) %s\n",
        $_, $stats{ $_ },
        $stats{ $_ } - ( 3 * $n ),
        '#' x abs( $stats{ $_ } - ( 3 * $n ) )
        for @data;
}

    [download]
    Over time, the variance should tend to converge towards zero for all choices, but every time I run this, one or two of the choices show no signs of converging. Indeed, their variance just seems to grow. Not mathematical proof of unfairness--I can't work out how to apply a Chi Squared test to this kind of data--but sufficient to convince me that there is something hookey.

    BTW, you'll need a wide terminal to see the effect at it's best. Mine is set to 1000 wide. Setting a small font also helps as the numbers grow.

    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.
[reply]
[d/l]
      I ran it on your solution and got similar results to those obtained by JavaFan's solution.. Maybe the test or the interpretation of the test is wrong. Looking at absolute numbers seems wrong.
[reply]
[d/l]
      Well, if my algorithm has a bias, it should be the same values that are picked more or less often than expected, each time you run the algorithm.

      Furthermore, I don't think abs($stats{$_} - 3 * $n) is what needs to converge towards zero; abs($stats{$_} - 3 * $n)/$n ought to converge towards zero. And that does.

[reply]
[d/l]
[select]
        it should be the same values that are picked more or less often than expected

        Agreed.

        abs($stats{$_} - 3 * $n)/$n ought to converge towards zero. And that does.

        Agreed. My test is broken. Using absolute variances instead of a percentages, hides that they actually do converge.

        Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
        "Science is about questioning the status quo. Questioning authority".
        In the absence of evidence, opinion is indistinguishable from prejudice.
[reply]

In Section Seekers of Perl Wisdom