R具有行限制的expand.grid

我有一个长度为N的数值向量x，并且想要创建以下所有集合的集合内和的向量：任何可能的x元素与最多M每个组合中的元素。我把一个缓慢的迭代方法放在一起;我在这里寻找的是一种不使用任何循环的方式。R具有行限制的expand.grid

考虑我已经采用的方法，在下面的例子中有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 < - 11:55代替x来观察这个）。理想情况下，会有一个expand.grid函数，它允许在构造完整矩阵之前对行进行限制，这至少可以保证矩阵大小在内存限制内。

有没有办法实现这一点，而不会导致大N的问题？

来源

2016-11-28 Jimmy

“11：15”令牌数据（per @ EtienneMoerman的优化）还是典型的真实数据？这有什么用？这是很难处理的2^45 – smci

试试这个：

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

来源

2016-11-28 13:01:47

伟大的答案的基数，谢谢！我应该提到，跟踪每个总和中的哪些元素也是有用的，但是我可以通过解决您的解决方案来实现这一点 - 在函数中添加更多行并再次使用combn来创建矩阵元素位置。 – Jimmy

您的问题与绝对数量的组合有关。你似乎在做的是以x的长度序列列出0和1的所有不同组合。

在你的例子中，x的长度是5，你有2^5 = 32的组合当x的长度是22时，你有2^22 = 4194304的组合。

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

它不会彻底解决你的问题，但你应该能够得到比现在还要进一步。

来源

2016-11-28 12:23:51

R具有行限制的expand.grid

回答

相关问题