Our purpose is to
sample()
function in R.PERMUTE(A)
------------
n = length(A)
for (i = 1, ..., n) {
SWAP(A, i, RANDOM(i, n))
}
The following is an R implementation of this algorithm.
random <- function(a, b)
{
a + floor(runif(1) * (b-a+1))
}
permute <- function(x)
{
n <- length(x)
for (i in seq_along(x))
{
s <- random(i, n)
x[c(i, s)] <- x[c(s, i)]
}
x
}
One example of runtime:
> system.time(permute(1:1000000))
user system elapsed
5.420 0.012 5.431
> system.time(sample(1:1000000))
user system elapsed
0.032 0.008 0.038
Run time as function of sample size: