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生成整个列表的函数(一个昂贵的操作).

Python标准库中的itertools模块是查找构造此类对象的指导的绝佳位置.Itertools已经部分重新实现为R作为同名包.

以下是使用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:"注意上面代码中的错误;我只是试过它,而不是证明它是正确的."

对于序列的前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上获得.如果有人有更好的主意,请分开!