python - 比赛问题

Question

我们有一个小任务来创建 n 支球队的锦标赛，每支球队必须在 o 场上按照 3 条规则进行 m 场比赛：

1. 一场比赛不得超过一次
2. 一支球队不能与自己对抗
3. 在锦标赛的任何给定时间，一支球队参加比赛的次数之差不能大于一。

下面的代码解决了这个问题，但显然非常非常慢。我知道有一个解决方案快一百万倍（并且也在 C++ 中，但我不相信这会产生超过一千倍的差异），但不知道该代码。

有没有人有关于使下面的代码更快的建议。应该进行回溯以寻找答案（允许的比赛）。Evaluate 查看锦标赛是否仍然允许，如果锦标赛仍然有效，extend 会继续（递归地）从 all_possible_games 堆栈中添加游戏。E 指定一个空字段，仅在最后一轮中允许。对于不同领域的 2-30 个团队等，该程序运行良好。但是 50 个球场上的 100 支球队，每支球队 10 场比赛应该可以在 0.001 秒内解决。这个程序需要几个小时...

import math


def printtournament(tournament):
    for gameround in grouped(tournament, fields):
        for game in sorted(gameround, key=lambda x: x[0] if isinstance(x[0], int) else 0):
            if game[0] != 'E':
                print(game, end='')
        print()
    print()


def grouped(iterable, n):
    return zip(*[iter(iterable)]*n)


def allgames(teamcount):
    games = []
    for t in range(teamcount):
        for u in range(teamcount):
            if u is not t:
                game = (u, t)
                game = sorted(game, reverse=False)
                if game not in games:
                    games.append(game)
    return games


def evaluate(tournament, fieldcount, gamesperteam, teamcount):
    current_games_per_team = {}

    for i in range(teamcount):
        current_games_per_team[i] = 0
    current_games_per_team['E'] = 0
    gamehasbeenplayed = []
    current_games_per_team_round = {}
    for i in range(teamcount):
        current_games_per_team_round[i] = 0
    current_games_per_team_round['E'] = 0

    for gameround in grouped(tournament, fieldcount):
        teamhasplayed = []

        for game in (gameround):
            for t in game:
                if t in teamhasplayed and t is not 'E':
                    return False
                else:
                    teamhasplayed.append(t)
            if game in gamehasbeenplayed and game[0] is not 'E' and game[1] is not 'E':
                return False
            else:
                gamehasbeenplayed.append(game)

            current_games_per_team[int(game[0]) if isinstance(game[0], int) else 'E'] += 1
            current_games_per_team[int(game[1]) if isinstance(game[0], int) else 'E'] += 1
            current_games_per_team_round[int(game[0]) if isinstance(game[0], int) else 'E'] += 1
            current_games_per_team_round[int(game[1]) if isinstance(game[0], int) else 'E'] += 1

            for k, c in current_games_per_team.items():
                if c > gamesperteam and k is not 'E':
                    return False

        for k1, c in current_games_per_team_round.items():
            for k2, d in current_games_per_team_round.items():
                if abs(c - d) > 1 and k1 is not 'E' and k2 is not 'E':
                    return False
    return True

def extend(gamecount, games, teams, fields, gamesperteam):
    if gamecount < games:
        for game in all_possible_games:
            tournament[gamecount] = game
            for i in range(fieldrounds):
                if i > gamecount:
                    tournament[i] = ['E', 'E']
            if evaluate(tournament, fields, gamesperteam, teams):
                extend(gamecount+1, games, teams, fields, gamesperteam)
    else:
        printtournament(tournament)


teams = 30
fields = 4
gamesperteam = 2
games = int(teams/2*gamesperteam)
fieldrounds = int(math.ceil(games/fields)*fields)
all_possible_games = allgames(teams)
tournament = []
for i in range(fieldrounds):
    tournament.append(['E', 'E'])

if __name__ == '__main__':
    extend(0, games, teams, fields, gamesperteam)

标签： pythonrecursiontimeexecution