Beefy Boxes and Bandwidth Generously Provided by pair Networks
XP is just a number
 
PerlMonks  

Re: random elements from array - new twist

by BrowserUk (Pope)
on Nov 05, 2002 at 06:02 UTC ( #210392=note: print w/ replies, xml ) Need Help??


in reply to random elements from array - new twist

One way would be to shuffle the elements of the array and then use a slice to assign them to your vars.

sub shuffle (\@) { my $r=pop; $a = $_ + rand @{$r} - $_ and @$r[$_, $a] = @$r[$a, $_] for (0..$#{$r}); } my @array = (1..15); shuffle(@array); my ($comp1, $comp2, $comp3, $comp4, $comp5) = @array[0..4];

Nah! Your thinking of Simon Templar, originally played by Roger Moore and later by Ian Ogilvy


Comment on Re: random elements from array - new twist
Download Code
Re: Re: random elements from array - new twist
by felwick (Sexton) on Nov 05, 2002 at 06:14 UTC
    success! big thanks.....
Re: Re: random elements from array - new twist
by IlyaM (Parson) on Nov 05, 2002 at 06:51 UTC
    BTW shuffle() subroutine is implemented in perl module List::Util. It is probably faster than your pure Perl implementation as it is written in C.

    --
    Ilya Martynov, ilya@iponweb.net
    CTO IPonWEB (UK) Ltd
    Quality Perl Programming and Unix Support UK managed @ offshore prices - http://www.iponweb.net
    Personal website - http://martynov.org

      use List::Util qw(shuffle); @a=qw(a b g f t h y); ($a,$b,$c) = @a[(shuffle(0..$#a))[0..2]]; print " $a $b $c ";
Re: Re: random elements from array - new twist
by Anonymous Monk on Nov 05, 2002 at 12:22 UTC
    You have a bad shuffle. It does not give equal odds of all combinations coming up. It trivially cannot, if your array has n elements then all of your probabilities have to be multiples of 1/n**n which does not evenly divide n! - the number of possible permutations you are choosing between.

    How to do it right is a FAQ.

      FWIW. To the best of my ability to test it, and walking on the shoulders of those better versed in statistics than I, my implementation of Fisher-Yates algorithm compares favourably with that given in the FAQ.

      Perhaps you would point out the flaws in my testing method?

      Test code

      C:\test>199981 -size=100 -iter=100000 Benchmark: running FAQ_FY, shuffl, each for at least 1 CPU seconds... FAQ_FY: 2 wallclock secs ( 1.14 usr + 0.00 sys = 1.14 CPU) @ 39 +2.64/s (n=448) shuffl: 1 wallclock secs ( 1.08 usr + 0.00 sys = 1.08 CPU) @ 44 +2.70/s (n=479) Rate FAQ_FY shuffl FAQ_FY 393/s -- -11% shuffl 443/s 13% -- permutation | FAQ_FY | shuffl ---------------------------------- A B C D: | 4140 | 4221 A B D C: | 4231 | 4211 A C B D: | 4205 | 4151 A C D B: | 4247 | 4257 A D B C: | 4076 | 4275 A D C B: | 4107 | 4244 B A C D: | 4207 | 4165 B A D C: | 4159 | 4240 B C A D: | 3941 | 4187 B C D A: | 4136 | 4116 B D A C: | 4158 | 4126 B D C A: | 4185 | 4111 C A B D: | 4126 | 4231 C A D B: | 4224 | 4122 C B A D: | 4135 | 4139 C B D A: | 4123 | 4097 C D A B: | 4179 | 4001 C D B A: | 4228 | 4175 D A B C: | 4295 | 4057 D A C B: | 4264 | 4131 D B A C: | 4206 | 4169 D B C A: | 4138 | 4239 D C A B: | 4167 | 4208 D C B A: | 4123 | 4127 ------------------------------------------------------ Std. Dev. | 72.382 | 67.643 C:\test>

      Nah! You're thinking of Simon Templar, originally played (on UKTV) by Roger Moore and later by Ian Ogilvy
        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}) - $_

        You are right...and accidentally demonstrated why you should break things out a little more and put in parens. I am a decent Perl programmer, and that code is unmaintainable.

        Just because Perl lets you do something doesn't mean that you should.

        "MAKEUP!", er, I mean, "Did somebody say 'Benchmark'?":
        use vars '@r'; sub supffl (\@) { local *r = pop; my $sz = @r; my $i = -1; while ($sz) { $a = ++$i + rand $sz--; @r[$i, $a] = @r[$a, $i]; } } =pod $ supshfl.pl Benchmark:running FAQ_FY, shuffl, supffl, each for at least 2 CPU sec FAQ_FY: 2 wc secs(2.19 usr + 0.00 sys = 2.19 CPU) @ 19.63/s (n=43) shuffl: 2 wc secs(2.13 usr + 0.00 sys = 2.13 CPU) @ 21.60/s (n=46) supffl: 2 wc secs(2.16 usr + 0.00 sys = 2.16 CPU) @ 23.15/s (n=50) Rate FAQ_FY shuffl supffl FAQ_FY 19.6/s -- -9% -15% shuffl 21.6/s 10% -- -7% supffl 23.1/s 18% 7% -- permutation | FAQ_FY | shuffl | supffl ------------------------------------------- ------------------------------------------- Std. Dev. | 6.404 | 6.397 | 5.746 =cut
        Though 20% hardly seems worth it.

        Basically, it's their efficiently checking for  $i == $j which slows down FAQ_FY!    mumble, mumble . . . premature optimization . . . mumble, mumble . . .
        sub FAQ_FY { my $array = shift; my $i; for ($i = @$array; --$i; ) { my $j = int rand ($i+1); # next if $i == $j; @$array[$i,$j] = @$array[$j,$i]; } } =pod $ supshfl.pl Benchmark:running FAQ_FY, shuffl, supffl, each for at least 1 CPU sec FAQ_FY: 1 wc secs(1.05 usr + 0.00 sys = 1.05 CPU) @ 21.90/s (n=23) shuffl: 1 wc secs(1.07 usr + 0.00 sys = 1.07 CPU) @ 21.50/s (n=23) supffl: 1 wc secs(1.04 usr + 0.00 sys = 1.04 CPU) @ 23.08/s (n=24) Rate shuffl FAQ_FY supffl shuffl 21.5/s -- -2% -7% FAQ_FY 21.9/s 2% -- -5% supffl 23.1/s 7% 5% -- permutation | FAQ_FY | shuffl | supffl -------------------------------------------- -------------------------------------------- Std. Dev. | 7.305 | 6.105 | 5.998 =cut

          p
Re: Re: random elements from array - new twist
by perlguy (Deacon) on Nov 05, 2002 at 23:30 UTC

    Forgive me, but why are you setting $a like this:
    $a = $_ + rand @{$r} - $_ and #...

    It seems to me that it should simply be:
    $a = rand @{$r} and #...

    Just a bit confused is all... clarify?

      It got me too (see Re: Re: Re: Re: random elements from array - new twist)... It's a matter of precedence. Have a look at how perl parses it:

      perl -MO=Deparse,-p -e "$a = $_ + rand @{$r} - $_" ($a = ($_ + rand((@{$r;} - $_)))); ^^ ^^ -e syntax OK

      The '- $_' is part of the argument to rand, not the assignment to $a.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://210392]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others browsing the Monastery: (5)
As of 2014-08-23 20:08 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The best computer themed movie is:











    Results (178 votes), past polls