每天将 X 个团队分成 3 个团队的数学解决方案
Mathematical solution to split X teams into 3 Teams per day
我正在尝试将 X 个团队分成 "play days"，每天 3 个团队
有不止一种解决方案可以解决 15 个团队的问题。
为 9-21 支队伍找到所有可能的 fixtures/match 计划的最佳方法是什么？
11、14、17 和 20 的团队数量也会导致问题，因为 total_matches/3="must be even/integer"
15 Teams // 105 Total Matches // 35 Total Days
D1 = 1:2 1:3 2:3
D2 = 2:4 2:5 4:5
D3 = 3:4 3:6 4:6
D4 = 4:1 4:7 1:7
D5 = 5:1 5:6 1:6
D6 = 6:2 6:7 2:7
7 = 7:3 7:5 3:5
8 = 8:1 8:9 1:9
9 = 9:2 9:10 2:10
10 = 10:1 10:11 1:11
11 = 11:2 11:8 2:8
12 = 12:1 12:13 1:13
13 = 13:2 13:14 2:14
14 = 14:1 14:15 1:15
15 = 2:12 2:15 12:15
16 = 3:8 3:10 8:10
17 = 3:9 3:11 9:11
18 = 3:12 3:14 12:14
19 = 4:8 4:12 8:12
20 = 5:8 5:13 8:13
21 = 6:8 6:14 8:14
22 = 7:8 7:15 8:15
23 = 9:4 9:13 4:13
24 = 9:5 9:12 5:12
25 = 10:4 10:14 4:14
26 = 11:4 11:15 4:15
27 = 12:6 12:10 6:10
28 = 13:3 13:15 3:15
29 = 14:5 14:11 5:11
30 = 5:10 5:15 10:15
D31 = 6:9 6:15 9:15
D32 = 6:11 6:13 11:13
D33 = 7:9 7:14 9:14
D34 = 7:10 7:13 10:13
D35 = 7:11 7:12 11:12
可能的 combinations/matches 支队伍的数量在数学上可以描述为 Triangular Number。
比如有9支队伍时，比赛场数为36场。
注意，当 k 或 k-1 能被 3 整除时，这个数字只能被 3 整除。有 5 支球队，你最终会有 10 场可能的比赛。您的最后一周将只有 1 场比赛，或者您可以采用不同的结构。
如果你想写出比赛的组合，你可以通过迭代两次球队的数量来列出它们。这是一些示例 Java 代码。 You may run it in an online Java compiler.
public class MyClass {
public static void main(String args[]) {
int TEAMS = 10; //Number of teams
int combos = 0;
for(int i = 1; i <= TEAMS-1; i++){
for(int j = i+1; j <= TEAMS; j++){
System.out.println("Team " + i + " plays Team " + j);
combos ++;
}
}
System.out.println("There is " + combos + " possible matches");
}
}
我们不只是想要 2 个团队的所有组合。我们想看看 3 支球队的组合。从数学上讲，我们想要 Combination.
我们可以将三角数改写为n选k。我们之前的例子变成：
我们选择的每周都有 3 支球队比赛。总可能的天组合是 n 选择 3。在我们的示例中有 9 个团队。
我们有 84 种可能的日期组合。这些日子中的许多日子都有重叠的游戏。例如，如果我们有 1、2 和 3 队比赛一天，那么我们不希望另一天有 1,2 和 4 队比赛，因为那样 1 队和 2 队会互相比赛 2 场比赛。解决方案可能是忽略重复的游戏。
我想指出，完美的解决方案是不存在的。对于大多数球队来说，没有一种解决方案可以每天让 3 支尚未参加过比赛的球队一起比赛。例如，当我们有 4 个团队时，我们的游戏是：
1-2、1-3、1-4、2-3、2-4、3-4。如果我们第一天选择了其中的 3 支球队（1-2、1-3、2-3），那么第二天我们就不会得到完美的组合（1-4、2-4、3-4）。
无论你如何破解它，你都可以对最佳组合进行排序，但最终你会得到许多随机游戏。
我在下面创建了代码来查看每个可能的日期组合并打印出不重复的日期。
public class MyClass {
public static void main(String args[]) {
int TEAMS = 9; //Number of teams
//Keep track of each game combination used
boolean gamesPlayed[][] = new boolean[TEAMS+1][TEAMS+1];
int day = 1;
for(int i = 1; i <= TEAMS-2; i++){
for(int j = i+1; j <= TEAMS-1; j++){
for(int k = TEAMS; k >= j+1; k--){
if(!gamesPlayed[i][j] && !gamesPlayed[i][k] && !gamesPlayed[j][k] )
{
System.out.println("Day "+ day++ + " Teams " + i + ", " + j + " & " + k + " Play");
gamesPlayed[i][j] = true;
gamesPlayed[i][k] = true;
gamesPlayed[j][k] = true;
}
}
}
}
System.out.println("\nLeftover games");
for(int i = 1; i <= TEAMS-1; i++){
for(int j = i+1; j <= TEAMS; j++){
if(! gamesPlayed[i][j])
System.out.println(" Team " + i + " plays Team " + j);
}
}
}
}
(Python) 以下根据目前为止比赛最少的球队选择接下来的三支球队每天进行分组，并给出了 9 支球队情况的理想解决方案：
from itertools import combinations
from string import ascii_uppercase
TEAMCOUNT = 9
teams = ascii_uppercase[:TEAMCOUNT] # Just use uppercase letters for teams
# All needed 2-team games
games = {''.join(two_teams) for two_teams in combinations(teams, 2)}
# All possible 3-team days and the 2-team matches they map to
triples = {x + y + z: {x+y, x+z, y+z}
for x, y, z in combinations(teams, 3) }
print('Teams:', teams)
n = 0
while games and triples:
# Weighting based on number of games left to play
weight = {t: sum(t in g for g in games) for t in teams}
to_play = {t1+t2: min([weight[t1], weight[t2]]) for t1, t2 in games}
# Choose teams that haven't played much next
_, chosen_triple = max((sum(to_play[m] for m in matches if m in games),
day)
for day, matches in triples.items())
n += 1
print(f" Day{n}: {chosen_triple} Games: ",
' '.join(sorted(m for m in triples[chosen_triple] if m in games)))
games -= triples[chosen_triple] # These games are played
del triples[chosen_triple] # This day triple used
if games:
print(" After those days, the following games remain to be played:", ' '.join(sorted(games)))
else:
print(" All games played!")
9 个团队的输出：
Teams: ABCDEFGHI
Day1: GHI Games: GH GI HI
Day2: DEF Games: DE DF EF
Day3: ABC Games: AB AC BC
Day4: CFI Games: CF CI FI
Day5: BEH Games: BE BH EH
Day6: ADG Games: AD AG DG
Day7: CEG Games: CE CG EG
Day8: BDI Games: BD BI DI
Day9: AFH Games: AF AH FH
Day10: CDH Games: CD CH DH
Day11: BFG Games: BF BG FG
Day12: AEI Games: AE AI EI
All games played!
我正在尝试将 X 个团队分成 "play days"，每天 3 个团队
有不止一种解决方案可以解决 15 个团队的问题。
为 9-21 支队伍找到所有可能的 fixtures/match 计划的最佳方法是什么？
11、14、17 和 20 的团队数量也会导致问题，因为 total_matches/3="must be even/integer"
15 Teams // 105 Total Matches // 35 Total Days
D1 = 1:2 1:3 2:3
D2 = 2:4 2:5 4:5
D3 = 3:4 3:6 4:6
D4 = 4:1 4:7 1:7
D5 = 5:1 5:6 1:6
D6 = 6:2 6:7 2:7
7 = 7:3 7:5 3:5
8 = 8:1 8:9 1:9
9 = 9:2 9:10 2:10
10 = 10:1 10:11 1:11
11 = 11:2 11:8 2:8
12 = 12:1 12:13 1:13
13 = 13:2 13:14 2:14
14 = 14:1 14:15 1:15
15 = 2:12 2:15 12:15
16 = 3:8 3:10 8:10
17 = 3:9 3:11 9:11
18 = 3:12 3:14 12:14
19 = 4:8 4:12 8:12
20 = 5:8 5:13 8:13
21 = 6:8 6:14 8:14
22 = 7:8 7:15 8:15
23 = 9:4 9:13 4:13
24 = 9:5 9:12 5:12
25 = 10:4 10:14 4:14
26 = 11:4 11:15 4:15
27 = 12:6 12:10 6:10
28 = 13:3 13:15 3:15
29 = 14:5 14:11 5:11
30 = 5:10 5:15 10:15
D31 = 6:9 6:15 9:15
D32 = 6:11 6:13 11:13
D33 = 7:9 7:14 9:14
D34 = 7:10 7:13 10:13
D35 = 7:11 7:12 11:12
可能的 combinations/matches 支队伍的数量在数学上可以描述为 Triangular Number。
比如有9支队伍时，比赛场数为36场。
注意，当 k 或 k-1 能被 3 整除时，这个数字只能被 3 整除。有 5 支球队，你最终会有 10 场可能的比赛。您的最后一周将只有 1 场比赛，或者您可以采用不同的结构。
如果你想写出比赛的组合，你可以通过迭代两次球队的数量来列出它们。这是一些示例 Java 代码。 You may run it in an online Java compiler.
public class MyClass {
public static void main(String args[]) {
int TEAMS = 10; //Number of teams
int combos = 0;
for(int i = 1; i <= TEAMS-1; i++){
for(int j = i+1; j <= TEAMS; j++){
System.out.println("Team " + i + " plays Team " + j);
combos ++;
}
}
System.out.println("There is " + combos + " possible matches");
}
}
我们不只是想要 2 个团队的所有组合。我们想看看 3 支球队的组合。从数学上讲，我们想要 Combination.
我们可以将三角数改写为n选k。我们之前的例子变成：
我们选择的每周都有 3 支球队比赛。总可能的天组合是 n 选择 3。在我们的示例中有 9 个团队。
我们有 84 种可能的日期组合。这些日子中的许多日子都有重叠的游戏。例如，如果我们有 1、2 和 3 队比赛一天，那么我们不希望另一天有 1,2 和 4 队比赛，因为那样 1 队和 2 队会互相比赛 2 场比赛。解决方案可能是忽略重复的游戏。
我想指出，完美的解决方案是不存在的。对于大多数球队来说，没有一种解决方案可以每天让 3 支尚未参加过比赛的球队一起比赛。例如，当我们有 4 个团队时，我们的游戏是： 1-2、1-3、1-4、2-3、2-4、3-4。如果我们第一天选择了其中的 3 支球队（1-2、1-3、2-3），那么第二天我们就不会得到完美的组合（1-4、2-4、3-4）。
无论你如何破解它，你都可以对最佳组合进行排序，但最终你会得到许多随机游戏。
我在下面创建了代码来查看每个可能的日期组合并打印出不重复的日期。
public class MyClass {
public static void main(String args[]) {
int TEAMS = 9; //Number of teams
//Keep track of each game combination used
boolean gamesPlayed[][] = new boolean[TEAMS+1][TEAMS+1];
int day = 1;
for(int i = 1; i <= TEAMS-2; i++){
for(int j = i+1; j <= TEAMS-1; j++){
for(int k = TEAMS; k >= j+1; k--){
if(!gamesPlayed[i][j] && !gamesPlayed[i][k] && !gamesPlayed[j][k] )
{
System.out.println("Day "+ day++ + " Teams " + i + ", " + j + " & " + k + " Play");
gamesPlayed[i][j] = true;
gamesPlayed[i][k] = true;
gamesPlayed[j][k] = true;
}
}
}
}
System.out.println("\nLeftover games");
for(int i = 1; i <= TEAMS-1; i++){
for(int j = i+1; j <= TEAMS; j++){
if(! gamesPlayed[i][j])
System.out.println(" Team " + i + " plays Team " + j);
}
}
}
}
(Python) 以下根据目前为止比赛最少的球队选择接下来的三支球队每天进行分组，并给出了 9 支球队情况的理想解决方案：
from itertools import combinations
from string import ascii_uppercase
TEAMCOUNT = 9
teams = ascii_uppercase[:TEAMCOUNT] # Just use uppercase letters for teams
# All needed 2-team games
games = {''.join(two_teams) for two_teams in combinations(teams, 2)}
# All possible 3-team days and the 2-team matches they map to
triples = {x + y + z: {x+y, x+z, y+z}
for x, y, z in combinations(teams, 3) }
print('Teams:', teams)
n = 0
while games and triples:
# Weighting based on number of games left to play
weight = {t: sum(t in g for g in games) for t in teams}
to_play = {t1+t2: min([weight[t1], weight[t2]]) for t1, t2 in games}
# Choose teams that haven't played much next
_, chosen_triple = max((sum(to_play[m] for m in matches if m in games),
day)
for day, matches in triples.items())
n += 1
print(f" Day{n}: {chosen_triple} Games: ",
' '.join(sorted(m for m in triples[chosen_triple] if m in games)))
games -= triples[chosen_triple] # These games are played
del triples[chosen_triple] # This day triple used
if games:
print(" After those days, the following games remain to be played:", ' '.join(sorted(games)))
else:
print(" All games played!")
9 个团队的输出：
Teams: ABCDEFGHI
Day1: GHI Games: GH GI HI
Day2: DEF Games: DE DF EF
Day3: ABC Games: AB AC BC
Day4: CFI Games: CF CI FI
Day5: BEH Games: BE BH EH
Day6: ADG Games: AD AG DG
Day7: CEG Games: CE CG EG
Day8: BDI Games: BD BI DI
Day9: AFH Games: AF AH FH
Day10: CDH Games: CD CH DH
Day11: BFG Games: BF BG FG
Day12: AEI Games: AE AI EI
All games played!