Создание случайных пар целых чисел без замены в R

Question

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

Представьте, например, что я хочу генерировать случайные пары целых чисел, используя последовательность целых чисел 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, это не так здорово.

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 

Answer 2

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

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 но в случайном порядке. Это то, что вы хотели?

Answer 3

Во-первых, я нашел, как сгенерировать пары на SO. Однако это не масштабировалось, поэтому я просмотрел ?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 

Answer 4

Как насчет:

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 возвращает матрицу вам нужно. Кажется, масштабируется нормально.

Answer 5

Вот моя попытка. Он выглядит не очень элегантно, но он все еще немного быстрее, чем @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 
    } 
}