Algoritmo per la generazione di un calendario di calcio This topic will discuss an algorithm, sin'ora unpublished, to generate a calendar of football.
The creator of this algorithm is Giuseppe Di Falco, a good professor of mathematics at the ITC, which I attended in the eighties.
Before proceeding to the actual description of the algorithm will try to explain what the problem be solved.
Given a number n of teams, you want to display a calendar, divided in n days, where each of n teams met once and only once all the others.
Each day will consist of n / 2 games and, if n is odd, a team 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.
write vertically names (in our case, as we have said, identified with numbers) of teams:
1 2
3 4 5
Imagining the above list as a "strip" fold, the break in two "turning" counter-clockwise in the second half so that it takes the following form:
5 14 23
What we got is the first day of the calendar: the first team playing against the fourth, the second against the third and fifth rests.
Now, keeping fixed the shape of our stric, 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
Rest team: 5
Day 2:
5-3
1-2
Rest team: 4
Day 3:
4-2
5-1
Rest Team: 3
Day 4:
3-1
4-5
Rest team: 2
Day 5:
2-5
3-4
Rest team: 1
Now we consider the case where n is even. We note, however, that if the "fix" the last team, making her play with the team that should rest in the case n-1, we would get in a totally automatic just the calendar you want to.
So, to fix ideas, suppose n = 6. As said, the timetable that we will be as follows:
Day 1:
6-5
1-4
2-3
Day 2:
6-4
5-3
1-2
Day 3:
6-3
4-2
5-1
Day 4:
6-2
3-1
4-5
Day 5:
6-1
2-5
3-4
Obviously, in any case, the total number of days (only the first round) will be: n - 1 + (n% 2).
Finally, we see an implementation in Java , released under 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
{System.out.println ("Warning: input parameter must be an integer between 1 and 99!");
return;}
} catch (Exception e) {
System.out.println ("Warning: input parameter must be an integer between 1 and 99!");
return;}
/ / Initialize the string of teams
String StringaSquadre = "";
for (int i = 1; the <=n; i++)
StringaSquadre + = ("" + String.valueOf (i)). substring ((" "+ String.valueOf (i)). Length () -2);
/ / Generate calendar
for (int i = 1; the <=n-1+(n%2); i++) {
System.out.println (" Day "+ 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 ("Rest the team:" + StringaSquadre . substring ((n - 1) * 2));
/ / Rotate the string of teams
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 ();
}
}
}
