R expand.grid 有行限制

Question

我有一个长度为 N 的数值向量 x，我想创建一个包含以下所有集合的集合内总和的向量：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

您的问题与组合的数量有关。您似乎在做的是在长度为 x.

的序列中列出 0 和 1 的所有不同组合

在您的示例中，x 的长度为 5，您有 2^5=32 种组合当 x 的长度为 22 时，您有 2^22=4194304 种组合。

您不能改用二进制编码吗？在你的情况下，这意味着 0代表00000 1代表00001 2代表00010 3代表00011 ...

它不会完全解决你的问题，但你应该能比现在更进一步。

Answer 2

试试这个：

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))))))

R expand.grid 有行限制

R expand.grid with row restrictions

combinations

r

matrix

subset-sum