所有可能的排列大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)"）