http://qs321.pair.com?node_id=210557


in reply to Re: Re: Re: random elements from array - new twist
in thread random elements from array - new twist

Your algorithm is not a Fisher-Yates shuffle. shuffl chooses a random number between 1 and the number of elements (inclusive) each time. A Fisher-Yates shuffle chooses from a smaller set each iteration to avoid performing a biased shuffle.

Using the dataset A, B, C and D there are 24 possible outcomes (4!), each one with an equal probability of 1/24. The algorithm used for sub shuffl selects 4 random numbers each with a possible value of 1, 2, 3 or 4, or a total of 44 (256) possible outcomes, each with a probability of 1/256 (some of the final permutations are duplicated). 256 is not evenly divisible by 24, so some of the outcomes must be more likely than others.

Update: Oops. BrowserUK's shuffle is indeed a Fisher-Yates shuffle. $a = $_ + rand @{$r} - $_ is parsed as $a = $_ + (rand @{$r} - $_). I assumed it would be parsed as $a = $_ + (rand @{$r}) - $_

Replies are listed 'Best First'.
Re: Re: Re: Re: Re: random elements from array - new twist
by BrowserUk (Pope) on Nov 05, 2002 at 20:06 UTC

    Look again!

    Update: Maybe this will clarify things a little?

    #! perl -sw use strict; sub shuffl (\@) { my $r=pop; for (0..$#{$r}) { my $size = scalar @{$r}; my $choices = $size - $_; printf 'iteration: %2d Size: %2d rand(%2d) range: %2d .. % +2d %s', $_, $size, $choices, $_, $cho +ices + $_, $/; $a = $_ + rand @{$r} - $_; @$r[$_, $a] = @$r[$a, $_]; } } my @array = (1 ..15); shuffl @array; __END__ C:\test>210557 iteration: 0 Size: 15 rand(15) range: 0 .. 15 iteration: 1 Size: 15 rand(14) range: 1 .. 15 iteration: 2 Size: 15 rand(13) range: 2 .. 15 iteration: 3 Size: 15 rand(12) range: 3 .. 15 iteration: 4 Size: 15 rand(11) range: 4 .. 15 iteration: 5 Size: 15 rand(10) range: 5 .. 15 iteration: 6 Size: 15 rand( 9) range: 6 .. 15 iteration: 7 Size: 15 rand( 8) range: 7 .. 15 iteration: 8 Size: 15 rand( 7) range: 8 .. 15 iteration: 9 Size: 15 rand( 6) range: 9 .. 15 iteration: 10 Size: 15 rand( 5) range: 10 .. 15 iteration: 11 Size: 15 rand( 4) range: 11 .. 15 iteration: 12 Size: 15 rand( 3) range: 12 .. 15 iteration: 13 Size: 15 rand( 2) range: 13 .. 15 iteration: 14 Size: 15 rand( 1) range: 14 .. 15 C:\test>

    Nah! You're thinking of Simon Templar, originally played (on UKTV) by Roger Moore and later by Ian Ogilvy