Kevin Old writes:
> On Wed, 2003-12-10 at 11:12, David Garamond wrote:
> > I'm trying to extend the Perl cookbook recipe on how to pick a random
> > line from a file:
> >
> > #!/usr/bin/perl
> > rand($.) < 1 && ($line = $_) while <>;
> > print $line;
> >
> > for picking up to N random lines from a file:
The classical algorithm for this is found in Knuth's "Art of computer
cproagramming, vol 2, seminumerical algorithms" on pp 121-123. Here
is a C++ routine I wrote several years ago that implements the
algorithm given in Knuth; perhaps it will help you write one in C:
9: // Knuth's random sample algotithm S, "Seminumerical Algorithms" pp 121-123.
10: //
11: void sample(prng rand, long* slot, long n, long N) { // take a random sample
12: long t; // counts up to N
13: long m = 0; // counts up to n
15: for (t = 0; m < n; t++) { // loop till all n slots are
chosen
16: if (rand.next(0, N - t) < n - m) { // do we select this from 0..N?
17: slot[m++] = t; // yes,
18: }
19: }
20: }
--
-------- "And there came a writing to him from Elijah" [2Ch 21:12] --------
R. J. Brown III [EMAIL PROTECTED] http://www.elilabs.com/~rj voice 847 543-4060
Elijah Laboratories Inc. 457 Signal Lane, Grayslake IL 60030 fax 847 543-4061
----- M o d e l i n g t h e M e t h o d s o f t h e M i n d ------
--
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
<http://learn.perl.org/> <http://learn.perl.org/first-response>
