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

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

Replies are listed 'Best First'.
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}) - \$_

"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
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.

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