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

Just don't shuffle the entire array; stop if you have shuffled three elements (taking care you don't shuffle in the leading animal). 
my @animals = qw [dog cat bird mouse rat snake horse cow
                  pig lizard lamb zebra lion elephant monkey];

my @scratch = @animals;

foreach my $animal (@animals) {
    for (my $j = @scratch - 1; $j >= @scratch - 3; $j --) {
        my $r = rand ($j + 1);
        @scratch[$j, $r] = @scratch[$r, $j];
        if ($scratch[$j] eq $animal) {
            my $r = rand ($j);
            @scratch[$j, $r] = @scratch[$r, $j];
        }
    }
    say "$animal @scratch[-3..-1]";
}

[download]
As one can see easily, the running time inside the main loop is independent of the size of the array, hence, O(1), making the entire program run in linear time.

Replies are listed 'Best First'.
Re^6: Array problem
by BrowserUk (Patriarch) on Sep 29, 2008 at 00:06 UTC
    As one can see easily, the running time inside the main loop is independent of the size of the array, hence, O(1), making the entire program run in linear time.

    Yep. Linear, but twice as slow as my code above for the OPs stated requirements: 

    c:\test>713977-javafan -N=1e6
Took 0.00029 seconds/iteration

c:\test>713977 -N=1e6
Took 0.00015 seconds/iteration

    [download]

    How much bigger than the requirements does the problem need to get before the additional complexity achieves parity?

    And how much bigger still, before the additional complexity of your solution starts to save enough time that the user will actually notice?

    Finally, what affect does that re-pick have upon the fairness of the shuffle?

    Read more... (2 kB)
    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]
[select]
      Oops, I was mistaken. I thought he was doing my $r = rand ($r);. I don't see any unfairness.
[reply]
[d/l]
        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]

      Finally, what affect does that re-pick have upon the fairness of the shuffle?

      Shuffling a previously fairly shuffled array should be as fair as shuffling the original. Right?

      What makes it unfair is the my $r = rand ($j);. It slightly favours anything preceding $animal in the array to shuffle.

[reply]
[d/l]
[select]
[reply]

In Section Seekers of Perl Wisdom