R: first N of all permutations

Question

I'm looking for a function that

• can list all n! permutations of a given input vector (typically just the sequence 1:n)
• can also list just the first N of all n! permutations

The first requirement is met, e.g., by permn() from package combinat, permutations() from package e1071, or permutations() from package gtools. However, I'm positive that there is yet another function from some package that also provides the second feature. I used it once, but have since forgotten its name.

Edit: The definition of "first N" is arbitrary: the function just needs an internal enumeration scheme which is always followed, and should break after N permutations are computed.

As Spacedman correctly pointed out, it's crucial that the function does not compute more permutations than actually needed (to save time).

Edit - solution: I remembered what I was using, it was numperm() from package sna. numperm(4, 7) gives the 7th permutation of elements 1:4, for the first N, one has to loop.

Answer 1

It seems like the best way to approach this would be to construct an iterator that could produce the list of permutations rather than using a function like permn which generates the entire list up front (an expensive operation).

An excellent place to look for guidance on constructing such objects is the itertools module in the Python standard library. Itertools has been partially re-implemented for R as a package of the same name.

The following is an example that uses R's itertools to implement a port of the Python generator that creates iterators for permutations:

require(itertools)

permutations <- function(iterable) {
  # Returns permutations of iterable. Based on code given in the documentation
  # of the `permutation` function in the Python itertools module:
  #   http://docs.python.org/library/itertools.html#itertools.permutations
  n <- length(iterable)
  indicies <- seq(n)
  cycles <- rev(indicies)
  stop_iteration <- FALSE

  nextEl <- function(){
    if (stop_iteration){ stop('StopIteration', call. = FALSE) }
    if (cycles[1] == 1){ stop_iteration <<- TRUE } # Triggered on last iteration

    for (i in rev(seq(n))) {
      cycles[i] <<- cycles[i] - 1
      if ( cycles[i] == 0 ){
        if (i < n){
          indicies[i:n] <<- c(indicies[(i+1):n], indicies[i])
        }
        cycles[i] <<- n - i + 1
      }else{
        j <- cycles[i]
        indicies[c(i, n-j+1)] <<- c(indicies[n-j+1], indicies[i])
        return( iterable[indicies] )
      }
    }
  }

  # chain is used to return a copy of the original sequence 
  # before returning permutations. 
  return( chain(list(iterable), new_iterator(nextElem = nextEl)) )

}

To misquote Knuth: "Beware of bugs in the above code; I have only tried it, not proved it correct."

For the first 3 permutations of the sequence 1:10, permn pays a heavy price for computing unnecessary permutations:

> system.time( first_three <- permn(1:10)[1:3] )
   user  system elapsed 
134.809   0.439 135.251 
> first_three
[[1]]
 [1]  1  2  3  4  5  6  7  8  9 10

[[2]]
 [1]  1  2  3  4  5  6  7  8 10  9

[[3]]
 [1]  1  2  3  4  5  6  7 10  8  9)

However, the iterator returned by permutations can be queried for only the first three elements which spares a lot of computations:

> system.time( first_three <- as.list(ilimit(permutations(1:10), 3)) )
   user  system elapsed 
  0.002   0.000   0.002 
> first_three
[[1]]
 [1]  1  2  3  4  5  6  7  8  9 10

[[2]]
 [1]  1  2  3  4  5  6  7  8 10  9

[[3]]
 [1]  1  2  3  4  5  6  7  9  8 10

The Python algorithm does generate permutations in a different order than permn.

Computing all the permutations is still possible:

> system.time( all_perms <- as.list(permutations(1:10)) )
   user  system elapsed 
498.601   0.672 499.284

Though much more expensive as the Python algorithm makes heavy use of loops compared to permn. Python actually implements this algorithm in C which compensates for the inefficiency of interpreted loops.

The code is available in a gist on GitHub. If anyone has a better idea, fork away!