R：所有排列的前 N ​​个

我正在寻找一个函数

• 可以列出所有n！给定输入向量的排列（通常只是序列1:n)
• 也可以只列出所有 n 中的前 N！排列

第一个要求得到满足，例如permn()从包装中combinat, permutations()从包装中e1071, or permutations()从包装中gtools。但是，我确信某个包中还有另一个功能也提供了第二个功能。我用过一次，但后来忘记了它的名字。

编辑： “前 N”的定义是任意的：该函数只需要一个始终遵循的内部枚举方案，并且应该在计算 N 个排列后中断。

正如 Spacedman 正确指出的那样，函数计算的排列数量不要超过实际需要的数量（以节省时间），这一点至关重要。

编辑-解决方案：我记得我正在使用什么，它是numperm()从包装中sna. numperm(4, 7)给出元素的第 7 个排列1:4，对于前 N 个，必须循环。

解决这个问题的最佳方法似乎是构建一个iterator可以生成排列列表，而不是使用类似的函数permn它预先生成整个列表（一个昂贵的操作）。

寻找构建此类对象的指导的一个很好的地方是迭代工具 http://docs.python.org/library/itertools.htmlPython 标准库中的模块。 Itertools 已针对 R 部分重新实现为同名的包 http://crantastic.org/packages/itertools.

下面是一个使用 R 的 itertools 实现 Python 生成器端口的示例，该生成器为排列创建迭代器：

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

}

错误引用Knuth http://en.wikiquote.org/wiki/Donald_Knuth：“小心上面代码中的错误；我只是尝试过，没有证明它是正确的。”

对于序列的前 3 个排列1:10, permn为计算不必要的排列付出沉重的代价：

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

但是，返回的迭代器permutations只能查询前三个元素，这样可以节省大量计算：

> 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

Python 算法确实以不同的顺序生成排列permn.

计算所有排列仍然是可能的：

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

尽管与 Python 算法相比，由于大量使用循环，成本要高得多permn。 Python 实际上用 C 语言实现了这个算法，弥补了解释循环的低效率。

代码可用GitHub 上的要点 https://gist.github.com/832723。如果有人有更好的想法，请离开！