I have n
可变长度的集合,并希望从每个集合中获取总和在一定范围内的所有项目排列。例如在R
我们可以做的:
set1 <- c(10, 15, 20)
set2 <- c(8, 9)
set3 <- c(1, 2, 3, 4)
permutations <- expand.grid(set1, set2, set3)
permutations$sum <- rowSums(permutations)
final <- permutations[permutations$sum >= 25 & permutations$sum <= 29, ]
# final:
# Var1 Var2 Var3 sum
# 3 20 8 1 29
# 5 15 9 1 25
# 8 15 8 2 25
# 11 15 9 2 26
# 14 15 8 3 26
# 17 15 9 3 27
# 20 15 8 4 27
# 23 15 9 4 28
这对于少量的集合来说是很好的,但是随着集合数量的增加,增长速度会很快(阶乘)。
是否可以生成适合约束的排列,而无需计算所有可能性?
在此示例中,不存在包含 10 个的最终组合set1
,因为无论选择哪个其他数字,所得的总和都太小。这对于缩小问题的范围可能很有用。例如,如果我知道min(set1) + max(set2) + max(set3) < 25 == TRUE
,那么我可以确保不包括min(set1)
在任何排列中。
我如何概括这一点,并使用约束来防止生成无效排列?
我认为你所要求的是相当具体的鞋拔子,不太可能“容易实施”(有效)。另一种看待它的方法是在运行实验时进行调节(假设这是试验设计)。
我写了一个lazyExpandGrid.R https://gist.github.com/r2evans/e5531cbab8cf421d14ed这在概念上类似于惰性expand.grid
,这意味着它不会预先评估所有可能的组合。如果需要,代码可以稍后插入到这个答案中,但是 github-gist 相当可靠(而且不短)。
使用它,您应该能够执行以下操作:
set1 <- c(10, 15, 20)
set2 <- c(8, 9)
set3 <- c(1, 2, 3, 4)
iter <- lazyExpandGrid(set1, set2, set3)
while (is.data.frame(item <- iter$nextItem())) {
p <- sum(item)
if (p < 25 || 29 < p) next
print(item) # but really, do something more interesting here
}
# Var1 Var2 Var3
# 3 20 8 1
# Var1 Var2 Var3
# 5 15 9 1
# Var1 Var2 Var3
# 8 15 8 2
# Var1 Var2 Var3
# 11 15 9 2
# Var1 Var2 Var3
# 14 15 8 3
# Var1 Var2 Var3
# 17 15 9 3
# Var1 Var2 Var3
# 20 15 8 4
# Var1 Var2 Var3
# 23 15 9 4
买者自负:该功能大部分可用,但肯定有一些方法可以改进。例如,使用is.data.frame(item <- iter$nextItem())
实际上是一个isTruthy
测试(名称来自shiny
);目前它返回 1 行data.frame
直到什么都没有剩下,然后返回FALSE
。现在看来,这肯定是可以改进的,只是我没有这个需要。如果您有想法、错误等,请随时在 github gist 页面上发表评论。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)