Friday, May 22, 2009

Algoritmo per la generazione di un calendario di calcio

In questo topic illustrerò un algoritmo, sin'ora inedito, per la generazione di un calendario di calcio.
L'ideatore di tale algoritmo è Giuseppe Di Falco, un bravo professore di matematica dell'ITC che ho frequentato negli anni ottanta.
Prima di passare alla descrizione vera e propria dell'algoritmo, cercherò di spiegare meglio qual'è il problema che si intende risolvere.
Dato un numero n di squadre, si desidera visualizzare un calendario, suddiviso in n giornate, in cui ciascuna delle n squadre incontra una ed una sola volta tutte le altre.
Ogni giornata sarà costituita da n/2 partite e, nel caso in cui n sia dispari, una squadra riposerà.
Al termine del girone, costituito dall'insieme delle giornate, tutte le squadre dovranno aver sfidato una ed una sola volta tutte le altre ed inoltre, sempre nel caso che il numero di squadre sia dispari, tutte dovranno aver riposato una ed una sola volta.
Ovviamente, il nome delle squadre non è importante: potremo riferirci a ciascuna di esse identificandole con un numero compreso tra 1 e n.
A questo punto, vediamo come funziona l'algoritmo in questione, riferendoci, per fissare le idee, ad un caso specifico.
Per comodità, prendiamo in esame prima il caso in cui n è dispari; quindi, a titolo di esempio, supponiamo n=5.
Scriviamo in verticale i nomi (nel nostro caso, come abbiamo detto, le identifichiamo con numeri) delle squadre:

1
2
3
4
5

Immaginando la suddetta lista come una "striscia" pieghevole, la spezziamo in due "ruotando" in senso antiorario la seconda metà in modo tale che essa assuma la seguente forma:

5
14
23

Quella che abbiamo ottenuto costituisce la prima giornata del calendario: la prima squadra gioca contro la quarta, la seconda contro la terza e la quinta riposa.

Ora, tenendo fissa la forma della nostra stricia, facciamo "slittare" in senso antiorario i nomi delle squadre che la compongono.
Così facendo, essa assumerà la seguente conformazione:

4
53
12

Questa costituisce la seconda giornata del nostro calendario.
Ripetendo tale operazione altre n-2 volte otterremo il girone di "andata" del nostro calendario. Non sarà necessario generare il girone di "ritorno" in quanto esso è identico a quello di andata con il solo scambio dei ruoli tra le squadre che giocano "in casa" e quelle che giocano "fuori casa".
In definitiva, quindi, l'output che otterremo sarà il seguente:


Giornata 1:
1 - 4
2 - 3
Riposa la squadra: 5

Giornata 2:
5 - 3
1 - 2
Riposa la squadra: 4

Giornata 3:
4 - 2
5 - 1
Riposa la squadra: 3

Giornata 4:
3 - 1
4 - 5
Riposa la squadra: 2

Giornata 5:
2 - 5
3 - 4
Riposa la squadra: 1


A questo punto, dovremmo esaminare il caso in cui n è pari. Possiamo notare, però, che se "fissiamo" l'ultima squadra, facendola giocare con la squadra che dovrebbe riposare nel caso n-1, otterremmo in modo del tutto automatico proprio il calendario che desideriamo.
Allora, per fissare le idee, supponiamo n=6. Per quanto detto, il calendario che otterremo sarà il seguente:

Giornata 1:
6 - 5
1 - 4
2 - 3

Giornata 2:
6 - 4
5 - 3
1 - 2

Giornata 3:
6 - 3
4 - 2
5 - 1

Giornata 4:
6 - 2
3 - 1
4 - 5

Giornata 5:
6 - 1
2 - 5
3 - 4

Ovviamente, in ogni caso, il numero totale delle giornate (del solo girone di andata), sarà: n - 1 + (n%2).
Per finire, vediamo un'implementazione in Java, rilasciata sotto Licenza GPL 3, come tutto il codice del software presente in questo blog, del suddetto algoritmo.



/**
* @author Andrea Pannitti
*
*/
public class CalendarioDiCalcio {

/**
* @param args
*/
public static void main(String[] args) {
int n;
//Controllo sul parametro di input
try {
n=Integer.parseInt(args[0]);
if (n<1 || n>99) {
System.out.println("Attenzione: il parametro di input deve essere un numero intero compreso tra 1 e 99!");
return;
}
}
catch (Exception e) {
System.out.println("Attenzione: il parametro di input deve essere un numero intero compreso tra 1 e 99!");
return;
}

//Inizializzazione della stringa delle squadre
String StringaSquadre = "";
for (int i=1; i<=n; i++)
StringaSquadre+=(" " + String.valueOf(i)).substring((" " + String.valueOf(i)).length()-2);

//Genera il calendario
for (int i=1; i<=n-1+(n%2); i++) {
System.out.println("Giornata " + i +":");

if (n%2==0)
System.out.println(StringaSquadre.substring((n - 1)* 2) + " - " + StringaSquadre.substring((n - 2) * 2, (n - 1) * 2));
for (int j=0; j<(int)((n-1)/2); j++) {
System.out.println(StringaSquadre.substring(j * 2, (j + 1)* 2) + " - " + StringaSquadre.substring((n - j - 3 + (n%2)) * 2, (n - j - 2 + (n%2)) * 2));
}
if (n%2==1)
System.out.println("Riposa la squadra: " + StringaSquadre.substring((n - 1) * 2));

//Ruota la stringa delle squadre
StringaSquadre = StringaSquadre.substring((n - 2 + (n%2)) * 2, (n - 1 + (n%2)) * 2) + StringaSquadre;
StringaSquadre = StringaSquadre.substring(0, (n - 1 + (n%2)) * 2) + StringaSquadre.substring(n * 2, (n + 1 - (n%2)) * 2);
System.out.println();
}
}
}

9 Comments:

At 4:11 AM, Blogger Tabris said...

grazie, algoritmo utile e ben illustrato

 
At 9:34 AM, Anonymous Anonymous said...

Creado che l'algoritmo non funzioni con 4 squadre infatti avremmo
giornata 1
23
14
giornata 2
34
21
giornata 3
41
32

Nella terza giornata abbiamo ancora 4 contro 1 anche se in ordine invertito, invece avremmo dovuto avere 1 contro 3
Cioa Mat

 
At 5:55 AM, Blogger Andrea Pannitti said...

Ciao Mat,
l'Algoritmo è corretto. Forse non ti è ben chiaro come funziona; d'altra parte puoi sempre sperimentarlo eseguendo il programma pubblicato.
Infatti, lanciado il suddetto programma, il risultato che otterresti con quattro squadre è il seguente:

Giornata 1:
4 - 3
1 - 2

Giornata 2:
4 - 2
3 - 1

Giornata 3:
4 - 1
2 - 3


Cordiali saluti,
Andrea Pannitti

 
At 7:00 AM, Anonymous Anonymous said...

che differenza c'è tra questo algoritmo e quello di Berger?

 
At 2:40 AM, Blogger Andrea Pannitti said...

Sinceramente, non conoscevo l'algoritmo di Berger.
Per tale motivo, quindi, non saprei dire se il professore del mio liceo già lo conoscesse o se è arrivato in modo indipendente allo stesso risultato; fatto stà che i due algoritmi mi sembrano equivalenti.

 
At 2:25 AM, Anonymous Anonymous said...

non credo funzioni come spiegato.

 
At 2:09 PM, Anonymous Anonymous said...

provate ad aggiungerci qualche vincoluccio tipo:
1) due squadre della stessa città devono giocare una in casa e l'altra fuori
2) una stessa squadra non può giocare più di due giornate consecutive fuori casa o in casa e questo deve capitare una sola volta in un girone di andata o ritorno
3) i derby non possono svolgersi nelle prime giornate o nelle ultime
e poi vedi che bel casino altro che algoritmo !!!

 
At 12:51 AM, Anonymous Anonymous said...

Non ti piaceva l'algoritmo di Berger?

https://it.wikipedia.org/wiki/Algoritmo_di_Berger

 
At 10:38 AM, Anonymous Anonymous said...

Arrivo un po' tardi (solo 13 anni dopo) però dopo aver scervellando un pomeriggio ho trovato questa pagina e l'algoritmo è perfetto. Per fare le cose più frizzanti ho rimescolato la lista di partenza e provato a generare andata e ritorno casuali con controllo (ed eventualmente scambio tra casa e trasferta) nel caso in cui la stessa partita sia stata giocata anche all'andata. È velocissimo anche con una lista di squadre molto lunga.

 

Post a Comment

<< Home