R: first N of all permutations

Question

I am looking for a function that

• can list all n! permutations of a given input vector (as a rule, only 1:n sequence)
• can also display only the first N of all n! Permutations

The first requirement is satisfied, for example, permn() from the combinat package, permutations() from the e1071 package e1071 or permutations() from the gtools package. However, I'm sure there is another function from some kind of package that also provides a second function. I used it once, but since then I forgot its name.

Edit: The definition of "first N" is arbitrary: a function just needs an internal enumeration scheme that is always respected and must be interrupted after calculating N permutations.

As Spacedman correctly pointed out, it is imperative that the function does not calculate more permutations than it actually does (in order to save time).

Edit - solution: I remember what I used, it was numperm() from sna package. numperm(4, 7) gives the 7th permutation of elements 1:4 , for the first N you need a loop.

Answer 1

It seems that the best way to approach this is to build an iterator that could create a permutation list, rather than using a function like permn that generates the entire list up (expensive operation).

A great place to look for guidance on creating such objects is the itertools module in the Python standard library. Itertools was partially reimplemented for R as a package with the same name .

The following is an example of using R itertools to implement a Python generator port 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)) ) } 

It is incorrect to use Knuth : "Beware of errors in the above code, I just tried, I did not prove that it is correct."

For the first 3 permutations of the 1:10 sequence, 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 only be requested for the first three elements, which eliminate a lot of computation:

 > 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 generates permutations in a different order than permn .

Computing all permutations is still possible:

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

Although much more expensive since the Python algorithm uses loops heavily compared to permn . Python actually implements this algorithm in C, which compensates for the inefficiency of interpreted loops.

The code is available in GitHub style . If anyone has a better idea, fork off!

Answer 2

In my version of R / combinat , the permn() function has a length of just over thirty lines. One way is to make a copy of permn and modify it to stop it earlier.