创建每个可能的团队组合 - 组合优化

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

每支球队不超过两名球员,每名球员至少1名,总薪水为36名.

我一直在尝试使用包来逐步实现所有~6MM组合的公式iterpc,查找并计算每一步的薪水/团队编号.这让我可以在每一步都将所有内容都安装到内存中,但速度非常慢且效率低下 - 这相当于创建了每个可能的团队并连续应用规则.

任何替代方法都会很棒!

Answer 1

设置添加七个收入最低的玩家,你得到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