Randomly Choose from an Array

[cylurian]

Hello everyone. How would I be able to choose randomly elements from
an array?

@r = (1, 2, 3, 4)

Randomly choose numbers and put back in the array

@r = (4, 2, 1, 3);

$p = $r[0]

print $p

 

[Mirco Wahab]

Hello everyone. How would I be able to choose
randomly elements from an array?
@r = (1, 2, 3, 4)

OK, this is rather simple:

...
@r = (1, 2, 3, 4);

$p = $r[ int rand @r ];
print $p;

Randomly choose numbers and put back in the array
@r = (4, 2, 1, 3);
$p = $r[0]
print $p

You could use 'shuffle' for that (as Glenn already said),
but also could do without:

...
@r = (1, 2, 3, 4);

@r = do {my @p; push @p, splice @r,int rand @r,1 while @r; @p};
print "$r[0] (@r)";

Regards

M.

 

[Mirco Wahab]

Mirco Wahab ([email protected]) wrote on MMMMCMII September MCMXCIII in
<URL:"" You could use 'shuffle' for that (as Glenn already said),
"" but also could do without:
"" @r = (1, 2, 3, 4);
"" @r = do {my @p; push @p, splice @r,int rand @r,1 while @r; @p};
"" print "$r[0] (@r)";

Yes, you could. But why would you want to use a quadratic algorithm
instead of a linear one?

Oops, I didn't really feel it would come out O(2) because I
thought the splice would find its elements in constant time.

But to be honest, I tried to give something like an 'alternative
formulation' for the 'shuffle', and the trivial solution like

my @r = (1, 2, 3, 4);

@r[$_->[0], $_->[1]] = @r[$_->[1], $_->[0]] for map [$_, int rand @r], 0..$#r;

was too much line noise (and some characters longer) ;-)

Thanks,

Mirco

 

[Mirco Wahab]

Mirco Wahab ([email protected]) wrote on MMMMCMII September MCMXCIII in
<URL@ But to be honest, I tried to give something like an 'alternative
@@ formulation' for the 'shuffle', and the trivial solution like
@@
@@ my @r = (1, 2, 3, 4);
@@
@@ @r[$_->[0], $_->[1]] = @r[$_->[1], $_->[0]] for map [$_, int rand @r], 0..$#r;

That's not a fair shuffle:

1 2 3 4: 977
...
4 3 2 1: 968

Shorter, and fair:

$r=@r;$i=rand$r--,@r[$i,$r]=@r[$r,$i]while$r;

Thats correct. My version from above over-generates
some pattern -- resulting in a wrong distribution.

I'm still struggling to see how your (wonderful)
example leads to equal distributed sets, but I
think (from intensive staring at your code) that
one has to 'move' both indexes with equal probability
in order to avoid overrepresentation of some sets.
(I'll look into this later ..)

Regards & thanks for this one ...

Mirco

 

[Ted Zlatanov]

Mirco Wahab ([email protected]) wrote on MMMMCMII September MCMXCIII in
<URL@ But to be honest, I tried to give something like an 'alternative
@@ formulation' for the 'shuffle', and the trivial solution like
@@ @@ my @r = (1, 2, 3, 4);
@@ @@ @r[$_->[0], $_->[1]] = @r[$_->[1], $_->[0]] for map [$_,
int rand @r], 0..$#r;

That's not a fair shuffle:

1 2 3 4: 977
...
4 3 2 1: 968

Shorter, and fair:

$r=@r;$i=rand$r--,@r[$i,$r]=@r[$r,$i]while$r;

MW> Thats correct. My version from above over-generates
MW> some pattern -- resulting in a wrong distribution.

MW> I'm still struggling to see how your (wonderful) example leads to
MW> equal distributed sets, but I think (from intensive staring at
MW> your code) that one has to 'move' both indexes with equal
MW> probability in order to avoid overrepresentation of some sets.
MW> (I'll look into this later ..)

The easiest way to prove it is correct (I think) is by induction. The
1-element case is obvious.

Basically for 2 elements you have a 50% chance they will be swapped:
$i is between 0 and 2 on the first cycle, 0 and 1 on the second (last)
cycle, so the first cycle has a 50$ chance of swapping and the second
(last) cycle always swaps.

Add 1 element. Now the first cycle has a 1/3 chance of swapping
elements $r[0] and $r[2] and 1/3 chance of swapping $r[1] and $r[2],
so the new (third and last) element $r[2] has equal chances of ending
up in any position. The second and third (last) cycles shuffle the
2-element array we already did.

Thus for N elements, the last one will have a 1/N chance of ending in
any position on the first cycle, and we take the first N-1 elements of
the resulting array to be shuffled fairly and independently by the
remaining cycles.

Like qsort, it's pretty simple once you see the pattern, but hell on
the braincells until you do

Ted