Random without replacement
Hi and thanks for reading this,
I need to generate random numbers without replacement (each new number can`t be repeated in the randomization process). Can anybody help me?
Thanks and best wishes
Bill Press
06-17-2007, 09:50 AM
Hi, Dan.
That is equivalent to generating a random permutation of the possible random values that you expect. This makes sense for integers in a given range (say 0 to 1000) but is hard to do if the set of possible values gets very large (say all 64 bit floating values). In the latter case, you might need to store generated values in a hash memory as they are generated, and skip repeats.
A standard algorithm for generating a random permutation is due to Knuth (see Wikipedia article Random Permutation). This is also covered in NR Third Edition, as is hash memory.
Cheers,
Bill P.
ambjorn
10-19-2007, 04:58 AM
You may also want to check out the papers below:
A Simple Method of Drawing a Sample Without Replacement A. C. Bebbington Applied Statistics, Vol. 24, No. 1. (1975), p. 136.
A Convenient Algorithm for Drawing a Simple Random Sample A. I. McLeod; D. R. Bellhouse Applied Statistics, Vol. 32, No. 2. (1983), pp. 182-184.
Ordered Random Selection Without Replacement A. F. Bissell Applied Statistics, Vol. 35, No. 1. (1986), pp. 73-75.