匹配顺序算法

Question

背景

我参与的一个体育俱乐部向我寻求帮助,为即将到来的比赛提供一些IT支持.

比赛由在比赛日之前不一定知道确切号码的队伍组成.因此需要软件帮助.

所有球队都将在许多比赛中与其他球队见面.因此,匹配的数量是N超过2(2的所有组合),其中N是团队的数量.

我们有不明数量的可用法院来比赛.可能这个数字将是1或可能2,但我想要一个通用的解决方案.

比赛将轮流进行.每回合将在每个球场上进行一场比赛.

例如,如果有两个球场和五个球队(A,B,C,D,E),转弯布局可能如下所示:

Turn      Court 1     Court 2
--------------------------------
 1        A vs B      C vs D
 2        A vs C      D vs E
 3        A vs D      B vs E
 4        B vs D      C vs E
 5        A vs E      B vs C

问题

因此,我的问题是找到一个生成一组符合以下简单规则的转弯的算法:

1. 所有球队必须在比赛期间恰好与其他所有球队会面一次.
2. 一支球队不能在同一回合打两场比赛(即在法院1和2上不能同时比赛)
3. 特定球队的转变应该在整个比赛中展开.

规则3详细说明

规则1和2非常简单,我已经有了解决方案.规则3给了我一些问题.我会尝试展示它的含义:

假设我有5支球队(如上所述),但只有1支球队.超过10回合有10场比赛.一种可能的布局是

Turn   Court 1
 1     A vs B
 2     A vs C
 3     A vs D
 4     A vs E
 5       .
 .       .
 .       .
 10      .

在这种情况下,A打前四场比赛是不公平的,因为他们没有机会在比赛之间恢复精力.这是我想要避免的.

想法？

Answer 1

如何为每个团队提供疲劳价值的简单贪婪解决方案.

首先,所有球队的疲劳设置为0.在转弯nr 1执行不同球场的初始比赛,并为这些球队设置与当前回合相同的疲劳值(第一场比赛中为1) .

反过来nr 2选择那些没有相互比较并且匹配它们的疲劳程度最低的队伍(通过保持队伍在例如优先级队列中).将疲劳值设置为当前转弯值.

通过您的示例,您将得到:

Turn     Court 1   Team:fatigue
0           -      A:0 B:0 C:0 D:0 E:0
1        A vs B    C:0 D:0 E:0 A:1 B:1
2        C vs D    E:0 A:1 B:1 C:2 D:2
3        E vs A    B:1 C:2 D:2 E:3 A:3
4        B vs C    D:2 E:3 A:3 B:4 C:4
5        D vs E    A:3 B:4 C:4 D:5 E:5
6        A vs C    B:4 D:5 E:5 A:6 C:6 // Dont match A with B since they already played, jump to team C
.

保持新鲜的团队始终在一开始.既然你可能不会超过100支队伍,那就足够了.