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

Question

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

Рассмотрим подход, который я использовал, в следующем примере с N=5 и M=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...

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