r - 创建每一种可能的团队组合——组合优化

Question

如果标题没有准确描述我正在做的事情，我深表歉意。

我正在尝试为梦幻体育比赛构建每一个可能的假设团队。这意味着要结合所有可用的球员，每个球员都有自己所在球队、位置和薪水等特征，这限制了一支球队的人数。我遇到的麻烦是找到一种有效内存的方法来将它们组合起来。

我制作了一个示例数据集:

 player_pool <- data.frame(id = seq(1,30), salary = seq(1,30), team = rep(LETTERS[seq(from=1, to=5)],6), position = rep(LETTERS[seq(from=1, to=5)],6))

在这 30 名球员中，我想选择每支 8 人的球队，所有 5 个角色中至少有 1 名球员，同一球队的球员不超过 3 名，总工资低于 50。

例如，这将是一个有效的团队:

 id salary team position
 1   1      A   A
 2   2      B   B
 3   3      C   C
 4   4      D   D
 5   5      E   E
 6   6      A   A
 7   7      B   B
 8   8      C   C

每队球员不超过两名，每个位置至少 1 名，总工资 36，不超过上限。

我一直在尝试实现一个公式，使用 iterpc 包逐步遍历所有 ~6MM 组合，在每一步查找并计算工资/团队数字。这让我可以将每一步的所有内容都放入内存中，但速度非常慢且效率低下——这相当于创建每个可能的团队并连续应用规则。

任何替代方法都会很棒!

Answer 1

设置将 7 名收入最低的球员加起来，得到 28。这意味着工资超过 22 的人都不能加入球队。

pool <- subset(player_pool,salary<=22)

寻找组合从这里开始，我会采取显而易见的路线，而不是寻找效率:

1. 识别所有行组合

   rs <- combn(seq(nrow(pool)),8)
   

2. 测试条件

   good_rs <- with(pool,apply(rs,2,function(x){
     sum(salary[x]) <= 50 &&
     length(unique(position[x])) == 5 &&
     max(lengths(split(x,team[x]))) <= 3
   }))
   

结果它运行得足够快(不到一秒)，我看到 339 个匹配的组合

length(which(good_rs))
# [1] 339