Como gerar automaticamente uma programação da liga esportiva

Question

Vou começar dizendo que entendo que esse tópico é complicado e que provavelmente não há uma resposta fácil. Se fosse fácil, todo mundo estaria fazendo isso. Sendo dito ...

Foi -me pedido para criar um aplicativo para gerenciar uma liga esportiva. A maioria dos conceitos é bastante fácil de entender, exceto para este: como gerar um cronograma de jogo onde não há sobreposições (a equipe joga 2 equipes ao mesmo tempo), onde uma equipe em uma divisão joga suas equipes duas vezes, mas joga equipes do Outras divisões uma vez e garante que não haja orifícios no cronograma (cada equipe joga toda semana)

No momento, o processo é feito manualmente usando uma planilha do tipo Rosetta Stone que eu construí para servir a esse fim, mas funciona apenas para o número de equipes para as quais foi projetado. Tenho variações feitas para 30 equipes, 24 equipes e 28 equipes. Em vez de tentar continuamente reajustar minha tabela de tradução, eu gostaria de poder codificar essa lógica e ajustar esse processo.

Pensamentos?

Answer 1

Existe um sistema bastante simples usado em torneios de xadrez, por exemplo, chamado Round-Robin.

A idéia é dividir os jogadores nos dois lados de uma mesa. Um dos jogadores é designado como um "hub" (por um desejo de uma palavra melhor). O torneio começa com jogadores enfrentando um contra o outro jogando um contra o outro. Após a primeira rodada, todos, exceto o hub, mova uma cadeira para frente e a ordem branca/preta (casa/fora do esporte) é trocada. Toda a competição de Round-Robin termina quando os jogadores ficam em seus lugares originais. Se você quer que todos joguem todo mundo duas vezes, faça o mesmo novamente.

Artigo da Wikipedia com detalhes da implementação.

No seu caso especial, eu tentaria fazer o Round Robin uma vez, incluindo todas as equipes. Então você faz o mesmo para cada divisão uma vez e para garantir que as equipes dentro das divisões se joguem uma vez em casa e uma vez, verifique a primeira rodada Robin de que maneira as equipes jogaram naquela rodada.

O lado de baixo disso é, é claro, que você jogará todas as partidas entre divisões bem antes dos acabamentos do torneio (já que as últimas partidas do N-1 são contra equipes intra-divisão [n = número de equipes na divisão]). Se isso for um problema, você pode simplesmente trocar um pouco de correspondência.

Na verdade, escrevi um script python simples que faz isso. Não foram necessárias muitas linhas de código e produziram bons resultados. Isso criará um cronograma em que cada equipe joga cada equipe em sua divisão duas vezes e uma vez contra equipes em outras divisões. Não há cheque para garantir que as equipes se encontrem duas vezes de tal maneira que a mesma equipe está em casa, no entanto. Mas esse código deve dar uma boa idéia sobre como criar seu próprio código de agendamento.

#!/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

Existem dois algoritmos, um para equipes ímpares, uma para equipes uniformes para garantir que o Round Robin aconteça.

Vou gerar um gráfico para você, se puder.

# Ímpar de equipes

O algoritmo é girar todas as equipes no sentido horário. Se tivéssemos 5 equipes:

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   

Nesse ponto, completamos um robin redondo onde todos jogam um ao outro uma vez ... a próxima rodada seria novamente ..

1 2
3 4
5

Mesmo nº de equipes

Quando temos um número uniforme de equipes, você faz a mesma rotação, exceto que mantém a equipe nº 1 na posição fixa e gira todas as outras equipes em torno de 1º lugar no sentido horário. Então, se tivéssemos 4 equipes ..

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

Este seria um Robin Round completo ... a próxima partida seria ..

1 2 
3 4 

Programaticamente, existem algumas maneiras de abordar isso. Talvez o código postado acima faça a mesma coisa lol ..

Answer 3

Eu apenas codificava essas restrições como uma fórmula booleana e usava algumas soluções de SAT para obter soluções (por exemplo, minisat para C ++, SAT4J para Java, e você poderia até escrever seu solucionador simples). A entrada para esses solucionadores é independente pelo DIMACS.

Veja também "Um SAT codificando o problema social do golfe" e "um agendador baseado no SAT para horários de torneios" para codificações de satélite de problemas semelhantes.

Answer 4

Aqui está uma chance de uma implementação

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 :)

Eu só testei no papel, mas para minha configuração ele funciona. Ao alternar entre começar no início da lista de equipes e no final da lista, evito as situações em que a mesma equipe teria que jogar o mesmo time repetidamente (ou jogar repetidamente no mesmo dia) no meu teste de papel I Representou todos os encontros possíveis como um oponente diferente, mas é basicamente o que o método Canplay deve fazer. Espero que isso ajude, apesar de não ser uma solução completa