Take the 2-minute tour ×

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.

share|improve this question
Am I missing something? Why not permutations(n)[1:N, ]? –  StompChicken Feb 17 '11 at 16:28
permutations(100,5)[1:10,] will take some times... I imagine thats the problem. –  Spacedman Feb 17 '11 at 16:55
You should probably have some sort of definition of what you mean by 'first'. –  John Feb 17 '11 at 16:56
@Spacedman exactly, @John edited my question to explain what I mean by "first". –  caracal Feb 17 '11 at 17:21
Perhaps you can code up Narayana Pandita's algorithm in R. en.wikipedia.org/wiki/…. Sort first and then apply algorithm. Comment instead of answer because i don't know R. Feel free to post an answer with this if you think it is suitable. –  Aryabhatta Feb 17 '11 at 17:22

2 Answers 2

up vote 5 down vote accepted

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:


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
        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  2  3  4  5  6  7  8 10  9

 [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  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!

share|improve this answer

In my version of R/combinat, the function permn() is just over thirty lines long. One way would be to make a copy of permn and change it to stop early.

share|improve this answer
That is a last resort. However, it makes communicating certain solutions more complicated when I have to include helper functions as well. Being able to just reference a CRAN-package for that task is less wordy and error-prone. –  caracal Feb 17 '11 at 19:10
For sure, if you can find an existing implementation, that's clearly the way to go (I had a quick look, and couldn't find one.) The real point of my answer was that in the absence of an existing implementation creating one that does exactly what you want is not that hard. –  NPE Feb 18 '11 at 10:47

Your Answer


