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.224 0.000 5.221
system.time(sample(1:1000000))
## user system elapsed
## 0.040 0.000 0.036
Run time as function of sample size:
etime <- function(n)
{
system.time(permute(1:n))["elapsed"]
}
N <- seq(1000, 100000, 5000)
T <- sapply(N, etime)
plot(N, T)
plot of chunk unnamed-chunk-3