赛事赛程管理器开发：如何高效筛选符合规则的有效赛程？

我正在开发一款赛事赛程管理器，为简化程序，设定小组内有4支队伍，采用主客场制，共6场比赛分6周进行。初始候选赛程的生成逻辑如下（代码与项目结构类似）：

from itertools import combinations

teams = ["Swin", "Lon", "Key", "Stran"]
dates = ["2023/05/17", "2023/05/22", "2023/05/29", "2023/05/17", "2023/05/22", "2023/05/29"]

possibilities = []
for the_date in dates:
  for match in combinations(teams, 2):
    possibilities.append({"Home": match[0], "Away": match[1], "Date": the_date})
    possibilities.append({"Home": match[1], "Away": match[0], "Date": the_date})

for i in  possibilities:
   print (i)

现需从上述候选赛程（possibilities）中筛选出满足以下规则的有效赛程集合：

• 任意两队的同一主客场组合不会重复出现两次；
• 同一日期内，主队和客队均不会参与两场比赛。

高效实现方法：回溯法+剪枝 #

直接暴力枚举所有6场比赛的组合效率极低，回溯法通过逐步构建赛程并实时检查规则，不符合就直接跳过（剪枝），能大幅减少无效计算，是这类组合筛选问题的高效解法。

核心思路

维护三个状态变量跟踪当前赛程的合规性，每一步选择比赛时先验证规则，符合条件再加入当前赛程，递归完成后回溯状态继续探索其他可能：

1. used_matches：用集合记录已经选过的主客场组合（比如(Home, Away)元组），确保不重复；
2. date_teams：用字典记录每个日期下已经参赛的队伍，键是日期，值是队伍集合，避免同一日期同一队打两场；
3. current_schedule：存储当前已构建的赛程列表，长度达到6时就是一个有效解。

代码实现

from itertools import combinations

teams = ["Swin", "Lon", "Key", "Stran"]
dates = ["2023/05/17", "2023/05/22", "2023/05/29", "2023/05/17", "2023/05/22", "2023/05/29"]

# 生成候选赛程
possibilities = []
for the_date in dates:
    for match in combinations(teams, 2):
        possibilities.append({"Home": match[0], "Away": match[1], "Date": the_date})
        possibilities.append({"Home": match[1], "Away": match[0], "Date": the_date})

valid_schedules = []

def backtrack(start_idx, used_matches, date_teams, current):
    # 凑够6场比赛，记录有效赛程
    if len(current) == 6:
        valid_schedules.append(current.copy())
        return
    
    # 从start_idx开始遍历，避免生成重复顺序的赛程（优化效率）
    for i in range(start_idx, len(possibilities)):
        match = possibilities[i]
        home, away, date = match["Home"], match["Away"], match["Date"]
        
        # 检查规则1：主客场组合未被使用过
        if (home, away) in used_matches:
            continue
        # 检查规则2：同一日期内两队都没参赛过
        if date in date_teams:
            if home in date_teams[date] or away in date_teams[date]:
                continue
        
        # 更新状态
        used_matches.add((home, away))
        if date not in date_teams:
            date_teams[date] = set()
        date_teams[date].update([home, away])
        current.append(match)
        
        # 递归构建下一场比赛
        backtrack(i + 1, used_matches, date_teams, current)
        
        # 回溯状态，探索其他可能
        current.pop()
        date_teams[date].remove(home)
        date_teams[date].remove(away)
        if not date_teams[date]:
            del date_teams[date]
        used_matches.remove((home, away))

# 启动回溯
backtrack(0, set(), {}, [])

# 示例输出
print(f"共找到{len(valid_schedules)}个有效赛程")
for idx, schedule in enumerate(valid_schedules[:3]):
    print(f"\n有效赛程{idx+1}:")
    for match in schedule:
        print(match)

额外优化点

• 可以先对候选赛程去重，提前移除重复的主客场+日期组合，减少遍历次数；
• 如果只需要部分有效赛程，找到目标数量后可以提前终止递归。

内容的提问来源于stack exchange，提问作者wantro