Answers are grounded in this paper and cite their sources.
A SAMPLE OF BRILLIANCEHow can a computer deal a poker hand?If we assign each card in the deck its own integer between 1 and 52, then we can make a hand from a "random sample" of 5 integers in the range 1..52, for instance, 4 a 31 46 47 (It is important that no number appear twice; holding more than one ace of spades can jeopardize a cardplayer's health.)Random samples also arise in applications such as simulation, program testing, and statistics.The first section of this column reviews several standard algorithms for random sampling.The next section describes an elegant new algorithm by Floyd.The third section describes how Floyd extends his algorithm to generate random permutations.A Sampling of Sampling Algorithms Before we can generate a random sample, we have to be able to generate a single random number.That topic is worth a column all its own, so we will simply assume that we have a function RandInt ( I, J ) that returns an integer uniformly distributed over I..J It is easy to generate a random sequence of M integers in the range l..N, so long as we don't mind duplicates for I := 1 to M do print RandInt(1, N)When I set M to 12 and N to 3, that code produced the sequence 313311121131 This very sequence might come in handy for your next tough game of rock-paper-scissors; more serious applications include testing finite state machines and sorting programs.Many applications, though, require a random sample without duplicates.A statistical analysis, for instance, might waste work by observing the same element twice.Such samples are often referred to as "samples without replacement" or as "combinations"; for the 0 1987 ACM OOOl-0782/0900-0754 $1.50 remainder of this column, though, the word "sample" will denote a random sample with no duplicates.The December 1984 column described several sampling algorithms.'The majority of the algorithms were based on the pseudocode in Algorithm S, which stores the sample in the set S. en ALGORITHM S.
No takes yet. Share an insight, caveat, or question.
Bentley et al. (1987) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: