R expand.grid с ограничениями строки

Question

У меня есть числовой вектор x длины N и хотел бы создать вектор внутри установленных сумм всех следующих наборов: любая возможная комбинация x элементов с не более M элементов в каждой комбинации. Я собрал медленный итеративный подход; то, что я ищу здесь, является способом, не использующим никаких циклов.

Рассмотрим подход Я принимаю, в следующем примере с N = 5 и М = 4

M <- 4 
x <- 11:15 
y <- as.matrix(expand.grid(rep(list(0:1), length(x)))) 
result <- y[rowSums(y) <= M, ] %*% x 

Однако, как N становится большим (более 22 для меня), выход становится expand.grid слишком большой и дает ошибку (замените x выше на x < - 11:55, чтобы это наблюдать). В идеале была бы функция expand.grid, которая допускает ограничения на строки перед построением полной матрицы, которая (по крайней мере, для того, что я хочу) будет поддерживать размер матрицы в пределах памяти.

Есть ли способ достичь этого, не вызывая проблем при больших N?

Answer 1

Попробуйте это:

c(0, unlist(lapply(1:M, function(k) colSums(combn(x, k))))) 

Он генерирует тот же результат, как с expand.grid подход, как показано ниже для данных испытаний.

M <- 4 
x <- 11:15 

# expand.grid approach 
y <- as.matrix(expand.grid(rep(list(0:1), length(x)))) 
result <- y[rowSums(y) <= M, ] %*% x 

# combn approach 
result1 <- c(0, unlist(lapply(1:M, function(k) colSums(combn(x, k))))) 

all(sort(result[,1]) == sort(result1)) 
# [1] TRUE 

Это должно быть быстрым (занимает 0.227577 секунд на моей машине, с N = 22, M = 4):

x <- 1:22 # N = 22 
M <- 4 
c(0, unlist(lapply(1:M, function(k) colSums(combn(x, k))))) 
# [1] 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 3 4 5 6 7 

вы можете выбрать уникальные значения сумм с

unique(c(0, unlist(lapply(1:M, function(k) colSums(combn(x, k)))))) 

Answer 2

Ваша проблема связана с огромным количеством комбинаций. Что вы делаете, это перечисление всех разных комбинаций 0 и 1 в последовательности длины x.

В вашем примере x имеет длину 5 и у вас есть 2^5 = 32 комбинации Когда x имеет длину 22, вы имеете комбинацию 2^22 = 4194304.

Не могли бы вы использовать двоичную кодировку? В вашем случае это будет означать 0 стендов для 00000 1 стендов для 00001 2 стендов для 00010 3 стендов для 00011 ...

Это не решит проблему полностью, но вы должны быть в состоянии получить немного дальше, чем сейчас.