所有可能的排列大n

Question

我想找到使用R大n所有可能的排列。此刻我使用permutations(n,n)从gtools包，但n>10几乎是不可能的;由于大量排列（n！），导致内存崩溃。我不想抽样，因为我需要找到特定统计的确切分布。有什么办法可以更快地做到这一点，或者我可以将它分解成小块？

Answer 1

你的目标很可能是不切实际的（“大n”有多大？即使你可以产生大量的排列，你需要多长时间才能总结出它们多少？在准确性上，将会有十亿个元素的穷尽计算和其中一千万个元素的随机抽样之间？）。但是：

iterpc软件包可以枚举块中的排列。例如：

library("iterpc") 

设置的对象（ “迭代”），以产生10个对象的排列：

I <- iterpc(10,labels=1:10,ordered=TRUE) 

返回所述第一5个排列：

getnext(I,5) 
##  [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] 
## [1,] 1 2 3 4 5 6 7 8 9 10 
## [2,] 1 2 3 4 5 6 7 8 10  9 
## [3,] 1 2 3 4 5 6 7 9 8 10 
## [4,] 1 2 3 4 5 6 7 9 10  8 
## [5,] 1 2 3 4 5 6 7 10 8  9 

返回下一个5排列：

getnext(I,5) 
##  [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] 
## [1,] 1 2 3 4 5 6 7 10 9  8 
## [2,] 1 2 3 4 5 6 8 7 9 10 
## [3,] 1 2 3 4 5 6 8 7 10  9 
## [4,] 1 2 3 4 5 6 8 9 7 10 
## [5,] 1 2 3 4 5 6 8 9 10  7 

假设您可以一次计算一个块的统计量，然后合并结果，这应该是可行的。但是，看起来并不像你可以很容易地并行化：无法跳转到迭代器的特定元素... sna包中的numperm函数提供对排列的“随机”（即非顺序）访问，虽然与iterpc给出的顺序不同 - 但我猜测iterpc效率要高很多，所以你最好在单个节点/核心/机器上顺序处理块，而不是分发进程。

这里是前5个排列由sna::numperm给出：

library("sna") 
t(sapply(1:5,numperm,olength=10)) 
##  [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] 
## [1,] 2 1 3 4 5 6 7 8 9 10 
## [2,] 2 3 1 4 5 6 7 8 9 10 
## [3,] 2 3 4 1 5 6 7 8 9 10 
## [4,] 2 3 4 5 1 6 7 8 9 10 
## [5,] 2 3 4 5 6 1 7 8 9 10 

的iterpc的胆量是用C++编写，所以它应该是非常有效的，但不管是什么事情会得到硬较大值为n。令我惊讶的是，iterpc可以处理的全套10 = 3628800个排列没有太多的麻烦！

system.time(g <- getall(I)) 
## user system elapsed 
## 0.416 0.304 0.719 
dim(g) 
## [1] 3628800  10 

不过，我不能在单块做任何的计算与n>10我的机器上（N = 11： "cannot allocate vector of size 1.6 Gb" ... n> 11 "The length of the iterator is too large, try using getnext(I,d)"）