•Re: Select three random numbers between 1..10

What ya need is a modified fisher-yates shuffle, shuffling only the part you're looking at:

my @population = (1..10); # destructive source
my $n = 3; # desired selection size
my @selection; # result appears here
while (@selection < $n) {
  my $swapper = int rand @population;
  push @selection, $population[$swapper];
  if ($swapper < $#population) {
    $population[$swapper] = $population[-1];
  }
  pop @population;
}
[download]

-- Randal L. Schwartz, Perl hacker
Be sure to read my standard disclaimer if this is a reply.

Comment on •Re: Select three random numbers between 1..10 Download Code

Replies are listed 'Best First'.
Re: Select three random numbers between 1..10 by Abigail-II (Bishop) on Mar 16, 2004 at 23:29 UTC
Urgle. While you pick a fast algorithm, your implementation is not efficient. There's no need to build @selection element by element, while popping off one element of of @population at the time. Just run `$n` iterations of Fisher-Yates loop, and return the last `$n` elements of the array. Furthermore, `if ($swapper < $#population) { $population[$swapper] = $population[-1]; }` [download] is less efficient than `$population[$swapper] = $population[-1];` [download] Sure, the if statement prevents a needless assignment, but the expected number of needless assignments is Σ_i=0^$n 1/(@population - i) which, while unbounded, grows very very slowly if the array to sample grows. OTOH, the number of compares done is linear with the size of the sample taken. Abigail	[reply] [d/l] [select]
•Re: Re: Select three random numbers between 1..10 by merlyn (Sage) on Mar 17, 2004 at 02:19 UTC
Oddly enough, Abi, I was hoping you'd point out the error of my ways. You have a brilliance that I can only aspire towards. I'm just a street-trained programmer of average class. -- Randal L. Schwartz, Perl hacker Be sure to read my standard disclaimer if this is a reply.	[reply]
Re: •Re: Select three random numbers between 1..10 by mstone (Deacon) on Mar 18, 2004 at 03:18 UTC
Out of curiosity, why did you choose to build a new list instead of transposing items within the existing one: `my @sample = (1..10); my $n = 3; for my $l (0..$n-1) { my $r = rand (@sample); @sample[ $l, $r ] = @sample[ $r, $l ]; } print join (", ", @sample[0..$n-1]), "\n";` [download] Transposition is safe against multiple hits to the same index, since each swap just shuffles the list a bit more. That eliminates the need to cull values that have already been seen, as you do with the `pop` at the tail of your loop. Even the degenerate case, where `$l` equals `$r`, leaves the list no less shuffled than it was before. And since every non-degenerate swap exchanges two values in the list, even the value left in place by a degenerate swap has a good chance of being moved by another, later swap.	[reply] [d/l]