Beefy Boxes and Bandwidth Generously Provided by pair Networks
more useful options
 
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 surveying the Monastery: (7)
As of 2015-07-04 03:32 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (57 votes), past polls