Выберите подмножество комбинаций

Question

Предположим, что у меня есть матрица 20 X 5, я хотел бы выбрать подмножества матрицы и выполнить некоторые вычисления с ними. Далее предположим, что каждая суб-матрица 7 X 5. Я мог бы, конечно, сделать

ncomb <- combn(20, 7) 

, который дает мне все возможные комбинации 7 индексов строк, и я могу использовать их для получения суб-матриц. Но с небольшой матрицей 20 X 5 уже существует 77520 возможных комбинаций. Поэтому я хотел бы случайным образом пробовать некоторые из комбинаций, например, 5000 из них.

Одна из возможностей заключается в следующем:

ncomb <- combn(20, 7) 
ncombsub <- ncomb[, sample(77520, 5000)] 

Другими словами, я могу получить все возможные комбинации, а затем случайным образом выбирать только 5000 комбинаций. Но я думаю, что было бы сложно вычислить все возможные комбинации, если бы у меня была большая матрица, скажем, 100 X 7.

Так что я задаюсь вопросом, есть ли способ получить подмножества комбинаций без предварительного получения всех возможных комбинаций.

Answer 1

я в конечном итоге делает то, что предложил @Roland, изменяя combn() и байт-компиляции кода:

combn_sub <- function (x, m, nset = 5000, seed=123, simplify = TRUE, ...) { 
    stopifnot(length(m) == 1L) 
    if (m < 0) 
     stop("m < 0", domain = NA) 
    if (is.numeric(x) && length(x) == 1L && x > 0 && trunc(x) == 
     x) 
     x <- seq_len(x) 
    n <- length(x) 
    if (n < m) 
     stop("n < m", domain = NA) 
    m <- as.integer(m) 
    e <- 0 
    h <- m 
    a <- seq_len(m) 
    len.r <- length(r <- x[a]) 
    count <- as.integer(round(choose(n, m))) 
    if(count < nset) nset <- count 
    dim.use <- c(m, nset)  

    ##-----MOD 1: Change the output matrix size-------------- 
    out <- matrix(r, nrow = len.r, ncol = nset) 

    if (m > 0) { 
     i <- 2L 
     nmmp1 <- n - m + 1L 

     ##----MOD 2: Select a subset of indices 
     set.seed(seed) 
     samp <- sort(c(1, sample(2:count, nset - 1))) 

     ##----MOD 3: Start a counter. 
     counter <- 2L  

     while (a[1L] != nmmp1) { 
      if (e < n - h) { 
       h <- 1L 
       e <- a[m] 
       j <- 1L 
      } 
      else { 
       e <- a[m - h] 
       h <- h + 1L 
       j <- 1L:h 
      } 
      a[m - h + j] <- e + j 

      #-----MOD 4: Whenever the counter matches an index in samp, 
      #a combination of row indices is produced and stored in the matrix `out` 
      if(samp[i] == counter){ 
       out[, i] <- x[a] 
       if(i == nset) break 
       i <- i + 1L 
      } 
      #-----Increase the counter by 1 for each iteration of the while-loop 
      counter <- counter + 1L 
     } 
    } 
    array(out, dim.use) 
} 

library("compiler") 
comb_sub <- cmpfun(comb_sub) 

Answer 2

Вашего подход:

op <- function(){ 
    ncomb <- combn(20, 7) 
    ncombsub <- ncomb[, sample(choose(20,7), 5000)] 
    return(ncombsub) 
} 

Другая стратегия, которая просто образцы семь строк из исходной матрицы 5000 раз (заменяя повторяющиеся образцы с новым образцом до 5000 уникальных комбинаций строк не найдены):

me <- function(){ 
    rowsample <- replicate(5000,sort(sample(1:20,7,FALSE)),simplify=FALSE) 
    while(length(unique(rowsample))<5000){ 
    rowsample <- unique(rowsample) 
    rowsample <- c(rowsample, 
        replicate(5000-length(rowsample), 
           sort(sample(1:20,7,FALSE)),simplify=FALSE)) 
    } 
    return(do.call(cbind,rowsample)) 
} 

Это должно быть более эффективным, поскольку оно не позволяет вам сначала вычислить все комбинации, что станет дорогостоящим по мере увеличения матрицы.

И все же некоторые бенчмаркинга показывают, что это не так. По крайней мере, на этой матрице:

library(microbenchmark) 
microbenchmark(op(),me()) 

Unit: milliseconds 
expr  min  lq median  uq  max neval 
op() 184.5998 201.9861 206.3408 241.430 299.9245 100 
me() 411.7213 422.9740 429.4767 474.047 490.3177 100