Как автоматически создать расписание спортивных лиг

Question

Начну с того, что понимаю, что эта тема сложна и, вероятно, не существует простого ответа.Если бы это было легко, то все бы это делали.Что, как говорится...

Меня попросили создать приложение для управления спортивной лигой.Большинство концепций довольно легко понять, за исключением этой:Как составить график игры, в котором нет совпадений (команда играет с двумя командами одновременно), где команда в дивизионе играет со своими командами дважды, а с командами из других дивизионов один раз, и следит за тем, чтобы в схеме не было дыр расписание (каждая команда играет каждую неделю)

Сейчас этот процесс выполняется вручную с использованием электронной таблицы типа Rosetta Stone, которую я создал для этой цели, но она работает только для того количества команд, для которых она была разработана.У меня есть вариации для 30 команд, 24 команд и 28 команд.Вместо того, чтобы постоянно пытаться корректировать свою таблицу перевода, я хотел бы иметь возможность систематизировать эту логику и вместо этого настроить этот процесс.

Мысли?

Answer 1

Существует довольно простая система, используемая, например.шахматные турниры, называемые круговыми.

Идея состоит в том, чтобы разделить игроков на две стороны стола.Один из игроков обозначен как «хаб» (за неимением лучшего слова).Турнир начинается с того, что игроки играют друг против друга.После первого раунда все, кроме хаба, передвигаются на один стул вперед, и порядок белый/черный (дома/гости в спорте) меняется.Все соревнования по круговой системе завершаются, когда игроки садятся на свои исходные места.Если вы хотите, чтобы все сыграли со всеми дважды, просто сделайте то же самое еще раз.

Статья в Википедии с подробностями реализации.

В вашем конкретном случае я бы попробовал провести круговую систему один раз, включив все команды.Затем вы делаете то же самое для каждого дивизиона один раз, и чтобы убедиться, что команды внутри дивизионов играют друг с другом один раз дома и один раз на выезде, проверьте по первому круговому турниру, как команды играли в этом раунде.

Обратной стороной этого, конечно, является то, что вы сыграете все матчи между дивизионами задолго до окончания турнира (поскольку последние n-1 матчей проводятся против команд внутри дивизиона [n = количество команд в дивизионе]).Если это проблема, вы можете просто немного поменять местами спички.

На самом деле я написал простой скрипт Python, который делает это.Это не заняло много строк кода и дало довольно хорошие результаты.Это создаст расписание, в котором каждая команда сыграет с каждой командой своего дивизиона дважды и один раз против команд из других дивизионов.Однако нет никакой проверки, позволяющей убедиться, что команды встречаются друг с другом дважды, чтобы одна и та же команда находилась дома.Но этот код должен дать хорошее представление о том, как создать собственный код планирования.

#!/usr/bin/python

div1 = ["Lions", "Tigers", "Jaguars", "Cougars"]
div2 = ["Whales", "Sharks", "Piranhas", "Alligators"]
div3 = ["Cubs", "Kittens", "Puppies", "Calfs"]

def create_schedule(list):
    """ Create a schedule for the teams in the list and return it"""
    s = []

    if len(list) % 2 == 1: list = list + ["BYE"]

    for i in range(len(list)-1):

        mid = int(len(list) / 2)
        l1 = list[:mid]
        l2 = list[mid:]
        l2.reverse()    

        # Switch sides after each round
        if(i % 2 == 1):
            s = s + [ zip(l1, l2) ]
        else:
            s = s + [ zip(l2, l1) ]

        list.insert(1, list.pop())

    return s


def main():
    for round in create_schedule(div1):
        for match in round:
            print match[0] + " - " + match[1]
    print
    for round in create_schedule(div2):
        for match in round:
            print match[0] + " - " + match[1]
    print
    for round in create_schedule(div3): 
        for match in round:
            print match[0] + " - " + match[1]
    print
    for round in create_schedule(div1+div2+div3): 
        for match in round:
            print match[0] + " - " + match[1]
        print

if __name__ == "__main__":
    main()

Answer 2

Существует два алгоритма: один для нечетных команд, другой для четных, чтобы обеспечить выполнение кругового турнира.

Если смогу, я сгенерирую вам графику.

НЕЧЕТНОЕ количество команд

Алгоритм заключается в ротации всех команд по часовой стрелке.Если бы у нас было 5 команд:

1 2 --> 3 1 --> 5 3 --> 4 5 --> 2 4
3 4     5 2     4 1     2 3     1 5
5       4       2       1       3   

На данный момент мы завершили один круговой турнир, в котором каждый играет друг с другом один раз...следующий раунд снова будет..

1 2
3 4
5

ЧЕТНОЕ количество команд

Когда у нас четное количество команд, вы выполняете ту же ротацию, за исключением того, что удерживаете команду №1 в фиксированном положении и вращаете все остальные команды вокруг №1 по часовой стрелке.Итак, если бы у нас было 4 команды..

1 2 --> 1 3 --> 1 4 
3 4     4 2     2 3 

Это будет один полный круговой турнир...следующий матч будет..

1 2 
3 4 

Программно есть несколько способов подойти к этому.Возможно, код, опубликованный выше, делает то же самое, лол..

Answer 3

Я бы просто закодировал эти ограничения в виде логической формулы и использовал какой-нибудь SAT-решатель для получения решений (например,MiniSAT для C++, SAT4J для Java, и вы даже можете написать свой собственный простой решатель).Входные данные для этих решателей стандартизированы DIMACS.

См. Также «Кодирование SAT для проблемы с социальным гольфистом» и «SAT-планировщик для графиков турнира» для SAT-кодировки аналогичных проблем.

Answer 4

вот пример реализации

public interface ITeam
{
   bool PlaysOn(DateTime date);
   bool canPlay(ITeam); //returns true if a game between the teams is legal (played once/twice   
                        //already, same different divisions and other applicable rules
}

IEnumerable<ITeam> teams = null; //replace with initialization
IEnumerable<ITeams> reversed = team.Reverse();
IEnumerable<DateTIme> gameDays = null;//replace with initialization
var count = teams.Count();

foreach(var date in gameDays)
{
   for(int i = 0;i<count;i++)
   {
      var innerTeams = i % 2 == 0 ? teams : reversed;
      var team = (from t in innerTeams
                  where !t.PlaysOn(date)
                  select t).First();  
      var opp = (from t in teams
                 where !t.PlaysOn(date) && t.CanPlay(team)
                 select t).First();
      SetupGame(team,opp);
   }
} //lot of optimazation possible :)

Я тестировал это только на бумаге, но для моей установки это работает.Чередуя начало списка команд и конец списка, я избегаю ситуаций, когда одной и той же команде придется играть с одной и той же командой снова и снова (или неоднократно играть в один и тот же день) в моем бумажном тесте. представлял каждую возможную встречу как другого противника, но это, по сути, то, что должен делать метод CanPlay.Надеюсь, это поможет, хотя это не полное решение.