Все возможные перестановки для больших n

Question

Я хочу найти все возможные перестановки для больших n с использованием R. На данный момент я использую permutations(n,n) от gtools, но для n>10 это почти невозможно; Я получаю сбои памяти из-за большого количества перестановок (n!). Я не хочу выбирать, поскольку мне нужно найти точное распределение для определенной статистики. Есть ли способ сделать это быстрее или что я могу разбить его на небольшие блоки?

Answer 1

Ваша цель очень вероятна быть непрактичной (насколько велика «большая n» ???, даже если вы можете создать огромное количество перестановок, сколько времени вам понадобится, чтобы суммировать их? в точности будет ли между исчерпывающим вычислением на миллиард элементов и случайной выборкой из десяти миллионов из них?). Однако:

Пакет iterpc может перечислить перестановки в блоках. Например:

library("iterpc") 

Настройка объект ("итератор"), чтобы генерировать перестановки 10 объектов:

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

Return первых 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 

Предполагая, что вы можете вычислить статистику по одному блоку за раз, а затем объединить результаты, это должно быть осуществимо. Это не похоже на то, что вы можете легко распараллеливать, хотя: нет возможности перейти к определенному элементу итератора ... Функция numperm из пакета sna обеспечивает «случайный» (то есть непоследовательный) доступ к перестановкам, хотя в другом порядке, чем у 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 в одном блоке на моей машине (п = 11: "cannot allocate vector of size 1.6 Gb" ... n> 11 "The length of the iterator is too large, try using getnext(I,d)")