用求和约束生成置换 [英] Generating permutations with a sum constraint

问题描述

我有n个可变长度的集合，并且想从总和在一定范围内的每个集合中获得项的所有排列.例如，在R中，我们可以做到:

I have n sets of variable length and would like to get all permutations of items from each set where the sum is within a certain range. For example in R we can do:

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

这对于少量的集合来说很好，但是随着(更大)集合的增加(部分)快速增长.

This is fine for a small number of sets, however quickly (factorially) grows with larger or a greater number of sets.

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

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

In this example, there are no final combinations containing the 10 from set1, as the resulting sum would be too small no matter which other numbers are chosen. This could be useful for reducing the scope of the problem. For example, if I know that min(set1) + max(set2) + max(set3) < 25 == TRUE, then I can make sure to not include min(set1) in any permutations.

如何对此进行概括，并使用约束条件来防止生成无效排列?

How can I generalize this, and use the constraints to prevent generating invalid permutations?

推荐答案

我认为您所要求的只是鞋拔子，不太可能轻松实施"(有效).观察它的另一种方法是在运行实验时进行条件处理(假设这是用于试验的设计).

I think what you're asking for is pretty shoe-horn specific and unlikely to be "easy to implement" (efficiently). A different way to look at it is to do the conditioning as you run the experiment (assuming this is a design for trials).

我写了一个 lazyExpandGrid.R ，它在概念上类似于懒惰的expand.grid ，表示它不会预先评估所有可能的组合.如果需要，可以在此答案的后面插入代码，但是github-gist非常可靠(而且不短).

I wrote a lazyExpandGrid.R that is similar in concept to a lazy expand.grid, meaning it does not evaluate all possible combinations up front. The code can be inserted later in this answer if needed, but the github-gist is fairly solid (and not short).

使用它，您应该能够:

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要点页面上发表评论.

Caveat emptor: the function is mostly usable, but there are certainly ways it can be improved. For instance, the use of is.data.frame(item <- iter$nextItem()) is effectively an isTruthy test (name from shiny); currently it returns a 1-row data.frame until nothing remains, then returns FALSE. As I look at it now, that can most certainly be improved, I just haven't had the need. Feel free to comment on the github gist page if you have thoughts, bugs, etc.

这篇关于用求和约束生成置换的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！