Вычислить N случайных перестановок вектора из 36 элементов

Question

У меня есть вектор V, содержащий 36 элементов, 18 - «0» и 18 - «1».Я хотел бы вычислить N случайных (не первых N) перестановок этого вектора.

Я мог бы сделать следующее:

library(combinat)
N <- 100 # or 200, 300, 500... max 1000
V <- c(rep(0, 18), rep(1, 18))
n <- factorial(36) # total number of unique possible permutations
p <- unique(permn(V))[sample(1:n, N)]

Но я быстро столкнулся с проблемой комбинаторного взрыва, так какsample(1:n, N) возвращает Error in 1:n : result would be too long a vector

и

permn(V) возвращает Error in vector("list", gamma(n + 1)) : vector size specified is too large

Есть ли другой (лучший) способ сделать это?

Answer 1

@ Джозеф Вуд получил идеальный ответ.На всякий случай, если вам нужен список этих выборок, используйте:

r <- RcppAlgos::permuteSample(0:1, freqs = c(18, 18), n = 100)
r <- lapply(1:dim(r)[1], function(x) {r[x,]})

Answer 2

Во-первых, нет результатов factorial(36), поскольку вы повторяете элементы.Если мы сделали, чтобы получить общее число, мы можем использовать пакет gmp, чтобы получить:

gmp::factorialZ(36)
Big Integer ('bigz') :
[1] 371993326789901217467999448150835200000000

То, с чем мы на самом деле имеем дело, называется перестановками мультимножеств (как указывает @JakubBucek в комментариях).Используя пакет RcppAlgos (который я создал) или пакет arrangements, мы можем легко и правильно рассчитать общее количество результатов и, что более важно, получить желаемые результаты.

Прежде всего, фактическиеколичество результатов:

arrangements::npermutations(0:1, freq = c(18, 18), bigz = TRUE)
Big Integer ('bigz') :
[1] 9075135300

RcppAlgos::permuteCount(0:1, freqs = c(18, 18))
[1] 9075135300

Это следствие комбинаторики.То есть мы должны разделить на произведение числа перестановок одинаковых элементов:

gmp::factorialZ(36) / gmp::pow.bigz(gmp::factorialZ(18), 2)
Big Rational ('bigq') :
[1] 9075135300

Теперь, чтобы сгенерировать ваши случайные перестановки.Для пакета arrangements мы используем аргумент nsample.Кроме того, мы можем установить начальное значение для воспроизводимости:

set.seed(123)
r1 <- arrangements::permutations(0:1, freq = c(18, 18), nsample = 10)

set.seed(123)
r2 <- arrangements::permutations(0:1, freq = c(18, 18), nsample = 10)

dim(r1)
[1] 10 36

identical(r1, r2)
[1] TRUE

## only showing 10 columns
head(r1[,1:10])
     [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
[1,]    0    0    0    0    1    1    0    1    1     1
[2,]    1    0    1    1    1    1    1    1    1     0
[3,]    0    0    0    0    0    1    1    0    0     0
[4,]    1    1    1    0    0    1    0    1    0     0
[5,]    0    1    1    0    0    1    1    1    0     1
[6,]    0    0    0    1    1    1    0    1    1     1

А для RcppAlgos мы вызываем permuteSample, используя аналогичные аргументы n и seed:

r3 <- RcppAlgos::permuteSample(0:1, freqs = c(18, 18), n = 10, seed = 42)
r4 <- RcppAlgos::permuteSample(0:1, freqs = c(18, 18), n = 10, seed = 42)

identical(r3, r4)
[1] TRUE

dim(r3)
[1] 10 36

Оба пакета также очень эффективны.Для генерации 1000 случайных перестановок требуется менее секунды:

system.time(RcppAlgos::permuteSample(0:1, freqs = c(18, 18), n = 1000))
 user  system elapsed 
0.051   0.000   0.052 

system.time(arrangements::permutations(0:1, freq = c(18, 18), nsample = 1000))
 user  system elapsed 
0.249   0.000   0.249