Rory
there are several packages that perform this.
I would use permn() of the combinat library, then, if
lexicographical order is important, sort it explicitly.
HTH
rksh
[EMAIL PROTECTED] wrote:
Hi all
Here is a rather naive implementation of the SEPA algorithm for generating
lexical permutations:
lexperm3 <- function(x, n=length(x)) {
perms <- list()
k <- 1
perms[[k]] <- x
k <- k + 1
for (y in 1:(factorial(n)-1)) {
i <- n-1
while (x[i] > x[i+1] && i > 0) {
i <- i - 1
}
# i is largest index st x[i] > x[i+1]
j <- n
# find min{ x[j], st n>=j>=i+1 and x[j]>x[i] }
while (x[j] <= x[i] && j > i) {
j <- j - 1
}
# swap x[i] and x[j]
tmp <- x[i];x[i] <- x[j]; x[j] <- tmp
# now sort everything from x[i+1]..x[n]
# by reversing the elements within
p <- i + 1
q <- n
while (p < q) {
tmp <- x[p]; x[p] <- x[q]; x[q] <- tmp
p <- p + 1
q <- q - 1
}
perms[[k]] <- x
k <- k + 1
}
perms
}
This, as you can imagine, is severely slow. I would like to speed up this
function if possible, which I guess would involve vectorizing the inner
loop..does anyone have any ideas about how to improve this code's runtime?
One small potential optimization I tried was to shorten the "sort by reverse
ordering" near the end of the inner loop : I tried replacing it with rev() and
sort(decreasing=TRUE) over a partial subset of the x vector: however rev() was much
slower, and I dont think sort() supports lexicographic ordering, so that didnt work.
Thanks
rory
Rory Winston
RBS Global Banking & Markets
280 Bishopsgate, London, EC2M 4RB
Office: +44 20 7085 4476
***********************************************************************************
The Royal Bank of Scotland plc. Registered in Scotland No 90312. Registered Office: 36 St Andrew Square, Edinburgh EH2 2YB.
Authorised and regulated by the Financial Services Authority
This e-mail message is confidential and for use by the=2...{{dropped:25}}
______________________________________________
R-help@r-project.org mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.
--
Robin K. S. Hankin
Uncertainty Analyst
University of Cambridge
19 Silver Street
Cambridge CB3 9EP
01223-764877
______________________________________________
R-help@r-project.org mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.