R help - Dec 2008 - Lexical Permutation Algorithm in R

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}}

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



Rory.WINSTON at rbs.com 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 at 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