On Wed, 12 Nov 2003, Liaw, Andy wrote: > As others already pointed out, the fast way is to use sample(). > > What I'd like to add is the following, which I learned from peeking at the C > code underneath sample(): To draw n samples without replacement from 1:N > (N>=n), you only need a loop from 1 to n that used up n random numbers. The > algorithm is simple, but IMHO very clever: > > pop <- 1:N > samp <- rep(NA, n) > soFar <- N > for (i in 1:n) { > idx <- ceiling(runif(1) * soFar) > samp[i] <- pop[idx] > ## swap the soFar-th and idx-th element of pop. > tmp <- pop[soFar] > pop[soFar] <- pop[idx] > pop[idx] <- tmp > ## decrease the population by 1. > soFar <- soFar - 1 > } > > This is obviously not efficient in high-level languages like R, but in terms > of algorithm, it is a lot more efficient than check-and-reject. IMHO this > should be described in some book, but I have not seen any book describing > it.
Ripley (1987) Stochastic Simulation, pp.80-1 for one. I am pretty sure it is Knuth's book, although I don't have that to hand. I attribute it to Moses & Oakford (1963). -- Brian D. Ripley, [EMAIL PROTECTED] Professor of Applied Statistics, http://www.stats.ox.ac.uk/~ripley/ University of Oxford, Tel: +44 1865 272861 (self) 1 South Parks Road, +44 1865 272866 (PA) Oxford OX1 3TG, UK Fax: +44 1865 272595 ______________________________________________ [EMAIL PROTECTED] mailing list https://www.stat.math.ethz.ch/mailman/listinfo/r-help