Турнирные проблемы

Question

У нас было небольшое задание для создания турниров из n команд, которые должны играть по m игр в каждой на кортах с 3 правилами:

1. В игру нельзя играть более одного раза
2. Команда не может играть против себя
3. Разница во времени, в которую играла команда, не может превышать единицу в любой момент времени в турнире.

Код ниже решает эту проблему, но, видимо, очень очень медленно.Я знаю, что есть решение примерно в миллион раз быстрее (и также в C ++, но я не верю, что оно имеет разницу более чем в тысячу раз), но я не знаю этого кода.

Кто-нибудь имеетпредложения по созданию ниже кода быстрее.Предполагается, что для поиска ответов (разрешенных турниров) необходимо вернуться назад.Оценка оценивает, разрешен ли турнир, расширяет, продолжает (рекурсивно) добавлять игры из стека all_possible_games, если турнир все еще подтверждается.E обозначает пустое поле, которое разрешено только в последнем раунде.Для 2-30 команд на разных полях и т. Д. Программа работает отлично.Но 100 команд на 50 кортах с 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)