计算36个元素的向量的N个随机排列

Question

我有一个包含36个元素的向量V，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

首先，没有factorial(36)结果，因为你有重复的元素。如果我们这样做，为了获得总数，我们可以使用gmp包来获得：

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

我们实际处理的是multisets的排列（正如@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

Answer 2

@Joseph Wood得到了完美的答案。如果您需要这些采样排列的列表，请使用：

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