我想绘制随机整数对而不替换(换句话说,我不希望有任何重复的对)。这个概念听起来很简单,但是我想不出一个快速简单的解决方案。

想象一下,例如,我想使用整数1:4的序列生成随机的整数对,以填充该对中的元素。还要假设我想生成5个随机对而不替换。然后,我希望能够生成类似这样的内容...

     [,1] [,2]
[1,]    1    2
[2,]    2    1
[3,]    3    3
[4,]    1    4
[5,]    4    3

在上面的示例中,没有重复的对(即行)。但是,上述矩阵的每一列中都有重复的整数。因此,使用sample()分别为每一列生成随机数将不起作用。

在我的上下文中不可行的另一个看似潜在的解决方案是生成许多对,其中包括重复项,然后追溯删除这些重复项。我无法执行此操作,因为我将需要生成特定数量的对。

我正在寻找解决此问题的有效方法。这似乎是一个简单的问题,它必须有一个简单的解决方案(即请不要嵌套for循环)

这是我的丑陋做法:
#This matrix maps a unique id i.e. (1:16) to a pair (i.e. the row & col of the matrix)
r.mat<-matrix(1:(4*4),4,4)
#Drawing a random id
r.id<-sample(r.mat,5,replace=FALSE)
#Mapping the random id to a random pair
r.pair<-t(sapply(r.id, function (x) which(r.mat==x,arr.ind=TRUE)))

这对于我的玩具示例来说可以很好地工作,但是当我想从序列1:10000000绘制大量对时,它并不是那么好。

最佳答案

这里的关键不是生成所有排列,因为这是非常昂贵的内存和时间。因为您只关心两个数字,所以只要(number_of_possible_values) ^ 2小于 double 浮点数中最大的可表示整数,我们就可以很容易地做到这一点:

size <- 1e5
samples <- 100
vals <- sample.int(size ^ 2, samples)
cbind(vals %/% size + 1, vals %% size)

基本上,我们使用整数表示值的每种可能组合。在我们的示例中,我们从直到1e5 ^ 2的所有数字中进行采样,因为我们有1e5 ^ 2可能是1e5数字的组合。这些1e10整数中的每一个都代表一种组合。然后,通过将模数作为第一个数字,将整数除法作为第二个数字,将该整数分解为两个分量值。

基准测试:
Unit: microseconds
                   expr        min         lq       mean
  funBrodie(10000, 100)     16.457     17.188     22.052
 funRichard(10000, 100) 542513.717 640647.919 638045.215

此外,限制应为〜3x1e7,并且保持相对较快:
Unit: microseconds
                  expr    min      lq     mean median      uq    max neval
 funBrodie(1e+07, 100) 18.285 20.6625 22.88209 21.211 22.4905 77.893   100

基准测试功能:
funRichard <- function(size, samples) {
  nums <- 1:size
  dt = CJ(nums, nums)
  dt[sample(1:dim(dt)[1], size = samples), ]
}
funBrodie <- function(size, samples) {
  vals <- sample.int(size ^ 2, samples)
  cbind(vals %/% size + 1, vals %% size)
}

并确认我们正在做类似的事情(请注意,这并非完全相同,但事实证明是这样):
set.seed(1)
resB <- funBrodie(1e4, 100)
set.seed(1)
resR <- unname(as.matrix(funRichard(1e4, 100)))
all.equal(resB, resR)
# TRUE

10-07 19:25
查看更多