r - 生成具有总和约束的排列

Question

我有 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

这对于少量集合来说很好，但是随着集合数量的增加或增加，它会快速(按因数)增长。

是否可以生成符合约束的排列，而不必计算所有可能性？

在此示例中，没有包含来自 set1 的 10 的最终组合。 ，因为无论选择哪个其他数字，结果总和都太小。这可能有助于缩小问题的范围。例如，如果我知道 min(set1) + max(set2) + max(set3) < 25 == TRUE ，那么我可以确保不包含 min(set1)在任何排列中。

我如何概括这一点，并使用约束来防止生成无效的排列？

Answer 1

我认为您所要求的非常具体，不太可能“易于实现”(有效)。另一种看待它的方式是在运行实验时进行调节(假设这是一个试验设计)。

我写了一个 lazyExpandGrid.R 这在概念上类似于懒惰的 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 页面上发表评论。