Генерация случайных пар целых чисел без замены в R

Я хочу нарисовать случайные целые пары без замены (иначе я не хочу дублировать пары). Эта концепция звучит просто, но я не могу придумать быстрое и простое решение.

Представьте, например, что я хочу генерировать случайные пары целых чисел, используя последовательность integer 1:4, чтобы заполнить элементы пары. Также предположим, что я хочу сгенерировать 5 случайных пар без замены. Затем я хочу иметь возможность генерировать что-то вроде этого...

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

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

Другое потенциально потенциальное решение, которое не будет работать для моего контекста, состоит в создании множества пар, которые включают дубликаты, а затем удаляют эти дубликаты ретроактивно. Я не могу этого сделать, потому что мне нужно будет генерировать определенное количество пар.

Я ищу эффективное решение этой проблемы. Это похоже на такой простой вопрос, оно должно иметь простое решение (т.е. Не нужно встраивать петли)

Вот мой уродливый подход:

#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, это не так уж хорошо.

Ответы

Ответ 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

Ответ 2

Сначала я нашел, как сгенерировать пары на fooobar.com/questions/510215/.... Однако это не масштабировалось, поэтому я просмотрел ?combn и нашел функцию expand.grid.

Далее я использую пакет data.table, потому что он хорошо справляется с большими данными (см. документацию по причине).

## the data.table library does well with large data sets
library(data.table)

## Small dummy dataset
pairOne = 1:10
pairTwo = 1:2
nSamples = 3

system.time({
dt = data.table(expand.grid(pairOne, pairTwo))
dt2 = dt[sample(1:dim(dt)[1], size = nSamples), ]
})
#   user  system elapsed 
#  0.002   0.001   0.001 

## Large dummy dataset
pairOne = 1:10000
pairTwo = 1:10000
length(pairOne) * length(pairTwo)
nSamples = 1e5
system.time({
dt = data.table(expand.grid(pairOne, pairTwo))
dt2 = dt[sample(1:dim(dt)[1], size = nSamples), ]
})
#   user  system elapsed 
#  2.576   1.276   3.862

Ответ 3

Вдохновленный Дэвидом Робинсоном первоначальный удар:

set.seed(1)
np <- 1000 # number of elements desired
M1 <- t(combn(1:np, 2))
sam <- sample(1:nrow(M1), np, replace = FALSE)
M2 <- M1[sam,]
anyDuplicated(M2) # returns FALSE

Это будет использовать все возможные записи M1, но в случайном порядке. Это то, что вы хотели?

Ответ 4

Здесь моя попытка. Он выглядит не очень элегантно, но он все же немного быстрее, чем @Richard Erickson (2.0s против 2.6s, для тех же размеров). Идея заключается в том, чтобы избежать создания перестановок, потому что это может занять много времени и использовать много памяти. Вместо этого я создаю две случайные выборки идентификаторов в заданном диапазоне и проверяю, дублируется ли какая-либо строка (что очень маловероятно для большого диапазона и средних выборок). Если они дублируются, то создается новый образец для столбца 2, и все повторяется.

range <- 1e8
n <- 1e5
ids1 <- sample(range, n)
ids2 <- sample(range, n)
mat1 <- cbind(ids1, ids2)
found = FALSE
while(!found) {
  if (any(duplicated(rbind(mat1, mat1[,2:1])))) {
    ids2 <- sample(range, n)
    mat1 <- cbind(ids1, ids2)
  } else {
    found=TRUE
  }
}

Ответ 5

Как насчет:

no.pairs.needed <- 4 # or however many you want
npairs<-0
pairs <- NULL
top.sample.range <- 10000  # or whatever

while (npairs < no.pairs.needed){
  newpair <- matrix(data=sample(1:top.sample.range,2), nrow=1, ncol=2)
 if(!anyDuplicated(rbind(pairs, newpair))){
    pairs <- rbind(pairs, newpair)
    npairs <- npairs+1
  }
}

Затем объект pairs вернет нужную вам матрицу. Кажется, масштабируется нормально.