创建所有可能的团队组合-组合优化 [英] Creating every possible team combination -- combinatorial optimization

问题描述

很抱歉，标题不是我正在做的事情的准确描述。

Apologies if the title is not an accurate description of what I'm doing.

我正在努力为幻想体育比赛组建所有可能的假想团队。这意味着要合并所有可用的球员，每个球员都有各自的特点，例如所在球队，位置和薪水，这限制了一个团队可以有多少名球员。我遇到的麻烦是找到一种有效的内存方式来将它们全部组合在一起。

I am trying to construct every possible hypothetical team for a fantasy sports competition. This means combining all available players, each of whom has characteristics like the team they are on, their position, and their salary, which limits how many can be on a single team. The trouble I am having is finding a memory efficient way to combine them all.

我创建了一个示例数据集：

I made an example dataset:

 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。

Out of these 30 players I would like to choose every team of 8, with at least 1 player from all 5 roles, no more than 3 players from the same team, and a combined salary of less than 50.

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

For example, this would be a valid team:

 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

每支球队最多两名球员，每个职位至少一名，工资总额为36。

No more than two players from each team, at least 1 of each position, and at 36 total salary, under the cap.

我一直在尝试实现一个逐步解决所有〜6MM组合的公式使用软件包 iterpc ，在每个步骤中查找并计算薪水/团队编号。这使我能够将每一步都存储到内存中，但是却非常缓慢且效率低下-等于创建了每个可能的团队并相继应用规则。

I have been trying to implement a formula which goes through all ~6MM combinations step by step using the package iterpc, looking up and calculating salary/team numbers at each step. This lets me fit everything into memory at each step, but is incredibly slow and inefficient -- it amounts to creating every possible team and applying the rules in succession.

任何替代方法方法会很棒！

Any alternate approaches would be great!

推荐答案

设置将七个收入最低的玩家加起来，您将获得28个。这意味着没有薪水高于22的一个人可以在团队中。

Setup Adding up the seven lowest-paid players, you get 28. This means that no one with a salary above 22 can be on the team.

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

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

Finding combos From here, I would take the obvious route instead of looking for efficiency:

1. 标识所有行组合

1. Identify all combos of rows

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

测试条件

Test conditions

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个匹配的组合

Results It runs fast enough (under a second), and I see 339 matching combos

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

这篇关于创建所有可能的团队组合-组合优化的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！