r - 在R中获取总和为274且最大值为4的所有组合

Question

我想获得 280 个元素的总和为 274 的所有组合，但每个值都必须是 0 到 4 之间的整数。

有一个函数几乎可以做到这一点，那就是restrictedparts(我在这里找到的:Getting all combinations which sum up to 100 using R)...但仍然必须只获取值不超过4的元素。

Answer 1

通常这些类型的问题可以通过 partitions 包来处理，但是，我无法找到使用该包的解决方案。我还不会完全排除这个包，因为在过去的几年里我不断发现真正的惊喜。我离题了。

首先，总和为 274 的正整数的最大数量为 274(例如 sum(rep(1, 274)))。因此，任何具有超过 274 个元素(例如 n)的解决方案都将是相同的，除了每个组合有额外的 n - 274 个零。

作为演示这一点的示例，假设我们正在寻找总和为 8 的 10 个元素的每种组合，其中每个元素都是 0 到 2 之间的整数。唯一的解决方案是:

     [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
[1,]    0    0    0    0    0    0    2    2    2     2
[2,]    0    0    0    0    0    1    1    2    2     2
[3,]    0    0    0    0    1    1    1    1    2     2
[4,]    0    0    0    1    1    1    1    1    1     2
[5,]    0    0    1    1    1    1    1    1    1     1

如您所见，最后一行具有最大数量的正元素(即 8 个)。

这是一个重要的观察结果，因为我们可以通过将元素数量限制为所需的总和来大大减少要测试的组合数量。

number of combinations with repetition n 个元素选择 k 由二项式系数给出，其中顶部数字为 n + k - 1，底部数字为 k:

因此，对于我们的示例，我们可以将可能的检查数量减少超过 2000 万次:

choose(280 + 5 - 1, 280)
[1] 265368251

choose(274 + 5 - 1, 274)
[1] 243531475

265368251 - 243531475
[1] 21836776

虽然我们已经减少了可能性的空间，但我们仍然面临着艰巨的任务。生成所有组合并测试它们的总和不太可能在合理的时间内产生任何解决方案。

使用较新版本的 RcppAlgos

更新了答案

在版本2.3.5中实现了非常高效的通用划分算法。它适用于带/不带重复的标准组合以及多重组合:

## Using version 2.4.1
system.time(comb274 <- RcppAlgos::comboGeneral(0:4, m = 274, TRUE, 
                                               constraintFun = "sum",
                                               comparisonFun = "==",
                                               limitConstraints = 274))
 user  system elapsed 
0.420   0.196   0.608

dim(comb274)
[1] 150811    274

还应该注意的是，我们不再需要限制结果，因为我们正在使用 std::vector::push_back()下。这是更可取的，因为 STL 向量增长非常有效，我们现在可以避免为 Rcpp::Matrix 预分配最大行数(这导致了我们在下面看到的内存耗尽)。

我们仍然可以通过使用合理的上限(即设置upper)来提高效率。在更高版本中执行此操作会调用 std::vector::reserve() :

system.time(comb274 <- RcppAlgos::comboGeneral(0:4, m = 274, TRUE, 
                                               constraintFun = "sum",
                                               comparisonFun = "==",
                                               limitConstraints = 274,
                                               upper = 1e6))
 user  system elapsed 
0.225   0.105   0.327

与旧版本相比，我们发现效率提高了约 10 倍。

v2.3.3

之前的RcppAlgos旧答案

更合理的解决方案是排除许多组合而不需要检查它们的总和。通过按字典顺序生成组合，一旦特定组合超出约束，我们就可以跳过许多组合，因为知道它们也会超出约束。这正是来自 RcppAlgos (我是作者)的 comboGeneral 所做的。

library(RcppAlgos) ## v2.3.2

comb274 <- comboGeneral(0:4, m = 274, TRUE, 
                        constraintFun = "sum",
                        comparisonFun = "==",
                        limitConstraints = 274)
Error: vector memory exhausted (limit reached?)

正如你所看到的，这在原始形式下是行不通的，因为有太多的组合需要测试(至少在我的机器上......你可以改变 macOS 上 R 的内存限制 R on MacOS Error: vector memory exhausted (limit reached?) ) .

这没问题。我们需要做的就是使用 upper 参数限制预期结果的数量。我就随意设置为100万。如果我们得到 100 万个结果，我们会增加此限制，直到结果数量小于我们的界限。

## Again, this was for v2.3.2
system.time(comb274 <- comboGeneral(0:4, m = 274, TRUE, 
                                    constraintFun = "sum",
                                    comparisonFun = "==",
                                    limitConstraints = 274,
                                    upper = 1e6))
 user  system elapsed 
3.624   0.079   3.705

dim(comb274)
[1] 150811    274

这就是你得到的!确认每行总和为 274，我们有:

all(rowSums(comb274) == 274)
[1] TRUE

如果您确实需要 280 个元素，您可以运行上述代码，将参数 m 设置为 280，但会牺牲效率，或者简单地 cbind 一个零矩阵comb274 有 150811 行和 6 列。