创造每一个可能的团队组合——组合优化

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 人，至少 1 名球员来自所有 5 个角色，同一队不超过 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

每支球队不超过2人，每个位置至少1人，工资总额36，在cap内。

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

任何替代方法都会很棒！

Answer 1

设置将薪水最低的七名球员加起来，得到28。这意味着薪水超过22的人都不能进入球队。

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

寻找组合从这里开始，我会选择明显的路线而不是寻找效率：

识别行的所有组合
```
rs <- combn(seq(nrow(pool)),8)
```

测试条件

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

创造每一个可能的团队组合——组合优化

Creating every possible team combination -- combinatorial optimization

simulation

combinations

r

combinatorics