Come generare automaticamente un programma di campionati sportivi

Question

Inizierò dicendo che capisco che questo argomento è complicato e che probabilmente non c'è una risposta facile. Se fosse facile, lo farebbero tutti. Detto questo ...

Mi è stato chiesto di creare un'applicazione per gestire un campionato sportivo. La maggior parte dei concetti sono abbastanza facili da capire tranne questo: come generare un programma di gioco in cui non ci sono sovrapposizioni (la squadra gioca 2 squadre contemporaneamente), dove una squadra in una divisione gioca le sue squadre due volte ma gioca le squadre dal altre divisioni una volta, e si assicura che non ci siano buchi nel programma (ogni squadra gioca ogni settimana)

In questo momento il processo viene eseguito manualmente utilizzando un foglio di calcolo di tipo rosetta stone che ho creato per questo scopo, ma funziona solo per il numero di team per cui è stato progettato. Ho fatto variazioni per 30 squadre, 24 squadre e 28 squadre. Piuttosto che tentare continuamente di regolare nuovamente la mia tabella di traduzione, vorrei essere in grado di codificare quella logica e modificare invece quel processo.

Pensieri?

Answer 1

Esiste un sistema piuttosto semplice utilizzato ad es. tornei di scacchi chiamati round-robin.

L'idea è quella di dividere i giocatori sui due lati di un tavolo. Uno dei giocatori è designato come "hub". (per mancanza di una parola migliore). Il torneo inizia con i giocatori uno di fronte all'altro che giocano uno contro l'altro. Dopo il primo round tutti tranne l'hub spostano una sedia in avanti e l'ordine bianco / nero (casa / fuori negli sport) viene commutato. L'intera competizione round-robin termina quando i giocatori si siedono nei loro posti originali. Se vuoi che tutti giochino due volte, fai di nuovo lo stesso.

Articolo di Wikipedia con dettagli di implementazione.

Nel tuo caso speciale, proverei a fare il round robin una volta includendo tutte le squadre. Quindi fai lo stesso per ogni divisione una volta e per assicurarti che le squadre all'interno delle divisioni si giochino una volta a casa e una volta fuori, controlla dal primo round robin come hanno giocato le squadre in quel round.

Il lato negativo di questo è, ovviamente, che giocherai tutte le partite tra le divisioni ben prima che il torneo finisca (dal momento che le ultime partite n-1 sono contro squadre intra-divisione [n = numero di squadre in divisione ]). Se questo è un problema, puoi semplicemente scambiare le partite un po '.

In realtà ho scritto un semplice script Python che lo fa. Non ci sono volute molte righe di codice e ha prodotto risultati abbastanza buoni. Questo creerà un programma in cui ogni squadra gioca ogni squadra nella loro divisione due volte e una volta contro squadre di altre divisioni. Non c'è controllo per assicurarsi che le squadre si incontrino due volte in modo tale che la stessa squadra sia a casa, comunque. Ma questo codice dovrebbe dare una buona idea su come creare il proprio codice di pianificazione.

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

Esistono due algoritmi, uno per le squadre dispari, uno per le squadre pari per assicurarsi che avvenga il round robin.

Ti genererò un grafico se posso.

ODD # di squadre

L'algoritmo è di ruotare tutte le squadre in senso orario. Se avessimo 5 squadre:

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   

A questo punto abbiamo completato un round robin in cui tutti si giocano una volta ... il prossimo round sarà di nuovo ..

1 2
3 4
5

ANCHE N. di squadre

Quando abbiamo un numero pari di squadre, fai la stessa rotazione, tranne che tieni la squadra n. 1 in posizione fissa e ruota tutte le altre squadre attorno al n. 1 in senso orario. Quindi, se avessimo 4 squadre ..

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

Questo sarebbe un round robin completo ... il prossimo incontro sarebbe ..

1 2 
3 4 

A livello di programmazione, ci sono alcuni modi in cui puoi affrontarlo. Forse il codice pubblicato sopra fa la stessa cosa lol ..

Answer 3

Vorrei solo codificare questi vincoli come formula booleana e utilizzare alcuni solutori SAT per ottenere soluzioni (ad esempio MiniSAT per C ++, SAT4J per Java, e potresti persino scrivere il tuo semplice risolutore). L'input di questi solutori è standardizzato da DIMACS.

Vedi anche " Una codifica SAT per il problema del golfista sociale " e "un programmatore basato su SAT per gli orari dei tornei" per codifiche SAT di problemi simili.

Answer 4

ecco uno scatto di un'implementazione

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

L'ho provato solo su carta ma per la mia installazione funziona. Alternando tra l'inizio all'inizio dell'elenco squadre e la fine dell'elenco, evito le situazioni in cui la stessa squadra dovrebbe giocare più volte la stessa squadra (o giocare più volte lo stesso giorno) nel mio test cartaceo I rappresentava ogni possibile incontro come un diverso opponnente ma questo è fondamentalmente ciò che dovrebbe fare il metodo CanPlay. Spero che questo aiuti, anche se non è una soluzione completa