# [R] repeat until function

Prof Brian Ripley ripley at stats.ox.ac.uk
Wed Nov 12 18:45:09 CET 2003

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,                  ripley at stats.ox.ac.uk
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