在R中生成随机的整数而不替换

Question

我想绘制随机整数对而无需替换(另一种方式我不想要任何重复对).这个概念听起来很简单,但我想不出一个快速而简单的解决方案.

想象一下,例如,我想使用整数序列生成随机的整数对,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中绘制大量对时,它并不是那么好.

Answer 1

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

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