algorithm - 每天将 X 个团队分成 3 个团队的数学解决方案
问题描述
我正在尝试将 X 支球队分成“比赛日”,每天由 3 支球队组成
对于 15 个团队,有不止一种解决方案可以解决这个问题。
为团队计数 9-21 找到所有可能的赛程/比赛计划的最佳方法是什么?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
解决方案
(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!
推荐阅读
- java - 如何查找 Chrome 驱动程序路径:驱动程序可执行文件不存在:错误
- vba - 使用 VBA 更新 Word 中 MERGEFIELDS 的值
- javascript - 如何使用 redux 更新全局状态并从全局状态中删除项目
- javascript - 输入使用 useRef 更改其值而不更新其状态
- reactjs - 使用 Object.keys React Realm 缓慢渲染
- php - 当“密钥存储库在 ./composer.json 中重复”时,composer 使用哪一个?
- html - 如何制作可点击的 HTML
- typescript - 将 switch 语句案例移动到自己的函数时出现 TypeScript 错误?
- php - PHP会话未显示值
- ios - 仅观看因缺少 HealthKit info.plist 键而被拒绝的应用程序二进制文件