R:所有排列中的前 N ​​个

Question

我正在寻找一个功能

可以列出所有 n!给定输入向量的排列(通常只是序列 1:n )

也可以只列出所有 n 的前 N!排列

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

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

正如 Spacedman 正确指出的那样，该函数不会计算出比实际需要更多的排列(以节省时间)，这一点至关重要。

编辑 - 解决方案:我记得我使用的是 numperm()来自包装 sna . numperm(4, 7)给出元素的第 7 次排列 1:4 ，对于第一个 N，必须循环。

Answer 1

似乎解决这个问题的最好方法是构造一个可以产生排列列表的迭代器，而不是使用像 permn 这样的函数。它会预先生成整个列表(一项昂贵的操作)。

itertools 是寻找有关构建此类对象的指导的好地方。 Python 标准库中的模块。 Itertools 已为 R 部分重新实现为 a package of the same name .

下面是一个使用 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)) )

}

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

对于序列的前 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

尽管与 permn 相比，Python 算法大量使用循环，因此成本更高。 . Python 实际上在 C 中实现了这个算法，它弥补了解释循环的低效率。

代码可用 in a gist on GitHub .如果有人有更好的主意，请 fork !