Il calendario Impossibile, un anno dopo
Salve a tutti;
Ripubblico un dilemma che ormai mi perseguita da diversi anni, l'anno scorso non ebbi esito positivo, anche perché forse spiegai in maniera difficile il problema. Questa volta cerco di essere più chiaro.
Il problema è il seguente:
Ci sono 12 squadre: (A, B, C, D,....., L)
Le 12 squadre devono affrontarsi in un girone all'italiana di sola andata (quindi 11 giornate)
Ogni giornata di campionato è composto da 3 fasce orarie in cui giocare (15:00, 18:00, 21:00), ad ogni fascia oraria si disputano 2 partite.
DOMANDA
E' possibile la creazione di un calendario in cui, oltre allo scontro diretto, ogni squadra gioca esattamente per 2 volte nella stessa fascia oraria con tutte le altre squadre?
Esempio per essere più chiaro
Giornata 1
Ore 15:00
A - B; C - D;
Ore 18:00
E - F; G - H;
Ore 21:00
I - J; K - L.
In questo esempio la squadra A gioca contro B (e non la deve più affrontare in campionato) e gioca nella stessa fascia oraria con C e D, quindi con queste ultime 2 squadre può giocarci soltanto un'altra volta nella stessa fascia oraria (escluso lo scontro diretto).
Credo di essere stato chiaro ed esaustivo e spero di incontrare qualche buon anima che risolva una volta per tutte questo problema (o al limite mi dimostra la sua infattibilità).
Ripubblico un dilemma che ormai mi perseguita da diversi anni, l'anno scorso non ebbi esito positivo, anche perché forse spiegai in maniera difficile il problema. Questa volta cerco di essere più chiaro.
Il problema è il seguente:
Ci sono 12 squadre: (A, B, C, D,....., L)
Le 12 squadre devono affrontarsi in un girone all'italiana di sola andata (quindi 11 giornate)
Ogni giornata di campionato è composto da 3 fasce orarie in cui giocare (15:00, 18:00, 21:00), ad ogni fascia oraria si disputano 2 partite.
DOMANDA
E' possibile la creazione di un calendario in cui, oltre allo scontro diretto, ogni squadra gioca esattamente per 2 volte nella stessa fascia oraria con tutte le altre squadre?
Esempio per essere più chiaro
Giornata 1
Ore 15:00
A - B; C - D;
Ore 18:00
E - F; G - H;
Ore 21:00
I - J; K - L.
In questo esempio la squadra A gioca contro B (e non la deve più affrontare in campionato) e gioca nella stessa fascia oraria con C e D, quindi con queste ultime 2 squadre può giocarci soltanto un'altra volta nella stessa fascia oraria (escluso lo scontro diretto).
Credo di essere stato chiaro ed esaustivo e spero di incontrare qualche buon anima che risolva una volta per tutte questo problema (o al limite mi dimostra la sua infattibilità).
Risposte
.
"sellacollesella":
Siccome nella successiva generazione dei "candidati calendari" fissavo la seconda squadra della prima partita ad \(n-1\), tra le \(315\) "giornate 0" di \(a_5\) in \(a_6\) ho selezionato le \(45\) con questa caratteristica, ossia \(1/(n-1)\).
Non ho capito cosa intendi con \(1/(n-1)\), forse volevi riferirti alle $45$ partite dell'elenco qui postato che hanno come prima partita $(0,7)$?
"sellacollesella":
Quindi, testando i rispettivi "candidati calendari", solamente \(6\) sono risultati compatibili con i vincoli imposti.
Precisamente come fai a passare da una generica "giornata 0" al rispettivo calendario?
Non mi sembra che sia un passaggio univoco, o sbaglio?
.
Hai messo i puntini sulle i, come si suol dire! 
E' qui che mi sorge qualche dubbio... per esempio, applicando il metodo da te descritto alla seguente "giornata 0", si ottiene:
che però non mi sembra un calendario valido (manca lo scontro $0-1$ per esempio). Ho frainteso qualcosa?
Io per la creazione dei calendari adopero il seguente schema:
dove fisso uno dei vertici (il $7$ in questo caso) e ruoto gli altri elementi.
Il punto però è che se fisso un altro vertice ottengo un calendario diverso.
"sellacollesella":
Ciò fatto, sono passato alla creazione dei rispettivi candidati calendari, dove per ogni giornata dalla \( 0 \) alla \( n-2 \) ho sostituito i numeri di \( a_6 \) con i resti delle divisioni per \( n-1 \) dei numeri stessi sommati al numero della giornata, quindi ho sovrascritto \( n-1 \) ad ogni seconda squadra della prima partita e ho sovrascritto \( n \) ad ogni \( 0 \), in modo da avere tutte le squadre con i numeri da \( 1 \) ad \( n \) (quest'ultimo passaggio è facoltativo).
E' qui che mi sorge qualche dubbio... per esempio, applicando il metodo da te descritto alla seguente "giornata 0", si ottiene:
GIORNATA 0: 0-7 2-6 1-4 3-5 GIORNATA 1: 1-7 3-0 2-5 4-6 GIORNATA 2: 2-7 4-1 3-6 5-0 GIORNATA 3: 3-7 5-2 4-0 6-1 GIORNATA 4: 4-7 6-3 5-1 0-2 GIORNATA 5: 5-7 0-4 6-2 1-3 GIORNATA 6: 6-7 1-5 0-3 2-4
che però non mi sembra un calendario valido (manca lo scontro $0-1$ per esempio). Ho frainteso qualcosa?
Io per la creazione dei calendari adopero il seguente schema:
G0 G1 G2 G3 G4 G5 G6 0-7 | 2-7 | 1-7 | 3-7 | 5-7 | 4-7 | 6-7 2-6 | 1-0 | 3-2 | 5-1 | 4-3 | 6-5 | 0-4 1-4 | 3-6 | 5-0 | 4-2 | 6-1 | 0-3 | 2-5 3-5 | 5-4 | 4-6 | 6-0 | 0-2 | 2-1 | 1-3
dove fisso uno dei vertici (il $7$ in questo caso) e ruoto gli altri elementi.
Il punto però è che se fisso un altro vertice ottengo un calendario diverso.
.
"sellacollesella":
Pertanto, io sarei dell'idea che quelle \( 45 \) candidate "giornate 0" siano da potare ulteriormente, eliminando quelle che non rispettano lo schema \( \frac{n}{2}-2 \) diagonali, \( 1 \) lato e \( 1 \) vertice - centro. Oppure, equivalentemente, considerarle tutte e \( 45 \) e verificare direttamente i candidati calendari tramite i quattro vincoli imposti nel modello di programmazione non lineare, intera e binaria, dato che ne tengono conto in automatico.
Non so, dovrei ragionarci un po'.
"sellacollesella":
Circa il tuo modo di "ruotare le squadre", non lo riesco a capire, non vedo il pattern che hai applicato.
Per esempio considerando la giornata $0$
0 Vs 7 2 Vs 6 1 Vs 4 3 Vs 5
è facile osservare che la giornata $1$
2 Vs 7 1 Vs 0 3 Vs 6 5 Vs 4
si ottiene tenendo il $7$ fisso e ruotando la sequenza $6,4,5,3,1,2,0$ in senso orario di una posizione.
"utente__medio":
Sto cercando di implementare un modo efficiente di generare le distinte "giornate 0" da cui ricavare i calendari da testare; in particolare ipotizzo che due "giornate 0" distinte debbano essere indipendenti dall'ordine delle fasce orarie, dall'ordine delle partite all'interno delle singole fasce orarie e dall'ordine delle squadre all'interno delle singole partite.
In pratica, detto $N$ il numero di squadre (indicate con i numeri che vanno da $0$ a $N-1$), ricavo l'elenco delle sequenze associate alle "giornate 0" in cui alla prima partita si incontrano le squadre $0$ e $N-1$. Una volta fissata la sequenza iniziale e una condizione di uscita, la definizione di ogni sequenza si basa esclusivamente sulla sequenza precedente sfruttando l'ordine delle partite.
Nel codice la funzione che se ne occupa è [inline]giornata_0_successiva()[/inline]; poi se volete approfondirne qualche punto, fatemi sapere.
Ora cambiamo argomento e consideriamo il seguente calendario trovato da @sellacollesella che è soluzione per $N=8$:
CALENDARIO-SOLUZIONE: 0-7 1-3 | 2-6 4-5 1-7 2-4 | 3-0 5-6 2-7 3-5 | 4-1 6-0 3-7 4-6 | 5-2 0-1 4-7 5-0 | 6-3 1-2 5-7 6-1 | 0-4 2-3 6-7 0-2 | 1-5 3-4
Partendo dalla "giornata 0"
0-7 1-3 | 2-6 4-5
le altre giornate possono essere ricavate dalla giornata precedente sostituendo ogni numero diverso da $N-1$ con il resto della divisione per $N-1$ del numero stesso incrementato di $1$.
Il problema è che questo metodo (chiamiamolo METODO_1) per ricavare un calendario da una generica "giornata 0" non sempre funziona:
"utente__medio":
applicando il metodo [...] alla seguente "giornata 0", si ottiene:
GIORNATA 0: 0-7 2-6 1-4 3-5 GIORNATA 1: 1-7 3-0 2-5 4-6 GIORNATA 2: 2-7 4-1 3-6 5-0 GIORNATA 3: 3-7 5-2 4-0 6-1 GIORNATA 4: 4-7 6-3 5-1 0-2 GIORNATA 5: 5-7 0-4 6-2 1-3 GIORNATA 6: 6-7 1-5 0-3 2-4
che però non mi sembra un calendario valido (manca lo scontro $ 0-1 $ per esempio).
Quindi METODO_1 non va bene, visto che non sempre restituisce un calendario valido, e ne va applicato uno diverso. Io per esempio per generare un calendario valido da una "giornata 0" utilizzo il seguente METODO_2:
"utente__medio":
[Per chiarezza la "giornata 0" è quella contenuta nelle prime due colonne]
G0 G1 G2 G3 G4 G5 G6 0-7 | 2-7 | 1-7 | 3-7 | 5-7 | 4-7 | 6-7 2-6 | 1-0 | 3-2 | 5-1 | 4-3 | 6-5 | 0-4 1-4 | 3-6 | 5-0 | 4-2 | 6-1 | 0-3 | 2-5 3-5 | 5-4 | 4-6 | 6-0 | 0-2 | 2-1 | 1-3
dove fisso uno dei vertici (il $ 7 $ in questo caso) e ruoto gli altri elementi.
Il punto però è che se fisso un altro vertice ottengo un calendario diverso.
A questo punto mi sorge un dubbio: se dalla "giornata 0"
0-7 1-3 | 2-6 4-5
volessi ricavare il calendario-soluzione prima postato utilizzando METODO_2, quale elemento dovrei fissare!? Non capisco perché non riesco ad ottenerlo!
In ogni caso, alla luce di ciò, per la generazione dei calendari mi sono visto costretto ad utilizzare METODO_1, e quindi oltre alla condizione imposta dall'OP (massimo due partite in contemporanea, escluso gli scontri diretti), vado anche a controllare che il calendario così ottenuto sia effettivamente valido.
Di seguito riporto il codice e l'output delle soluzioni per $N=4,8,12,16$:
#include <iostream>
#include <iomanip>
using namespace std;
const unsigned int N = 8;
bool giornata_0_successiva(unsigned int v[N])
{
bool u[N] = {};
u[v[N - 1]] = u[v[N - 2]] = true;
for(unsigned int i = N - 3; i != 1; --i)
{
u[v[i]] = true;
if(i % 4)
{
for(unsigned int j = v[i] + 1; j < N; ++j)
{
if(u[j] && (i % 2 || v[i + 1] != j))
{
v[i++] = j;
u[j] = false;
if(!((i - 1) % 2))
{
while(!u[++j]);
v[i++] = j;
u[j] = false;
}
for(unsigned int k = 1; i < N; u[k] ? v[i++] = k++ : ++k);
return true;
}
}
}
}
return false;
}
bool testa_calendario(const unsigned int v[N])
{
unsigned int m_1[N][N] = {};
unsigned int m_2[N][N] = {};
for(unsigned int i = 0; i < N - 1; ++i)
{
for(unsigned int j = 0; j < N; j += 4)
{
unsigned int s1 = (v[j] + i) % (N - 1);
unsigned int s2 = j ? (v[j + 1] + i) % (N - 1) : N - 1;
unsigned int s3 = (v[j + 2] + i) % (N - 1);
unsigned int s4 = (v[j + 3] + i) % (N - 1);
if((s1 < s2 ? ++m_1[s2][s1] : ++m_1[s1][s2]) == 2 ||
(s3 < s4 ? ++m_1[s4][s3] : ++m_1[s3][s4]) == 2 ||
(s1 < s3 ? ++m_2[s3][s1] : ++m_2[s1][s3]) == 3 ||
(s1 < s4 ? ++m_2[s4][s1] : ++m_2[s1][s4]) == 3 ||
(s2 < s3 ? ++m_2[s3][s2] : ++m_2[s2][s3]) == 3 ||
(s2 < s4 ? ++m_2[s4][s2] : ++m_2[s2][s4]) == 3)
{
return false;
}
}
}
return true;
}
void stampa_giornata_0(const unsigned int v[N], const unsigned int n)
{
cout << n << ":\t";
for(unsigned int i = 0; i < N; ++i)
{
cout << (i && !(i % 4) ? " | " : "") << setw(2) << v[i] << (!(i % 2) ? "-" : " ");
}
cout << "\n";
}
int main()
{
if(N && !(N % 4))
{
unsigned int v[N] = {0, N - 1};
for(unsigned int i = 2; i < N; v[i] = i - 1, ++i);
unsigned int n_c = 0;
unsigned int n_s = 0;
do
{
++n_c;
if(testa_calendario(v))
{
stampa_giornata_0(v, ++n_s);
}
}
while(giornata_0_successiva(v));
cout << "\nNUMERO DI CALENDARI TESTATI: " << n_c << "\n";
}
}1: 0- 3 1- 2 NUMERO DI CALENDARI TESTATI: 1 Process returned 0 (0x0) execution time : 0.014 s
1: 0- 7 1- 3 | 2- 6 4- 5 2: 0- 7 1- 5 | 2- 3 4- 6 3: 0- 7 2- 3 | 1- 5 4- 6 4: 0- 7 2- 6 | 1- 3 4- 5 5: 0- 7 4- 5 | 1- 3 2- 6 6: 0- 7 4- 6 | 1- 5 2- 3 NUMERO DI CALENDARI TESTATI: 45 Process returned 0 (0x0) execution time : 0.021 s
1: 0-11 1- 3 | 2- 9 6- 7 | 4-10 5- 8 2: 0-11 1- 4 | 2- 6 3- 8 | 5- 7 9-10 3: 0-11 1- 7 | 2- 5 3-10 | 4- 6 8- 9 4: 0-11 1- 8 | 2- 3 5- 7 | 4-10 6- 9 5: 0-11 2- 3 | 1- 8 5- 7 | 4-10 6- 9 6: 0-11 2- 5 | 1- 7 8- 9 | 3-10 4- 6 7: 0-11 2- 6 | 1- 3 4- 7 | 5-10 8- 9 8: 0-11 2- 8 | 1- 4 5- 6 | 3-10 7- 9 9: 0-11 3- 9 | 1- 8 2- 4 | 5- 6 7-10 10: 0-11 3-10 | 1- 7 2- 5 | 4- 6 8- 9 11: 0-11 4- 5 | 1-10 2- 8 | 3- 7 6- 9 12: 0-11 4- 6 | 1- 7 8- 9 | 2- 5 3-10 13: 0-11 4-10 | 1- 8 6- 9 | 2- 3 5- 7 14: 0-11 5- 7 | 1- 8 6- 9 | 2- 3 4-10 15: 0-11 5- 9 | 1- 6 2- 3 | 4- 7 8-10 16: 0-11 6- 7 | 1-10 3- 9 | 2- 5 4- 8 17: 0-11 6- 9 | 1- 8 5- 7 | 2- 3 4-10 18: 0-11 7-10 | 1- 2 4- 6 | 3- 8 5- 9 19: 0-11 8- 9 | 1- 7 2- 5 | 3-10 4- 6 20: 0-11 8-10 | 1- 7 3- 6 | 2- 9 4- 5 NUMERO DI CALENDARI TESTATI: 14175 Process returned 0 (0x0) execution time : 0.061 s
1: 0-15 1- 2 | 3- 6 9-11 | 4-13 8-12 | 5-10 7-14 2: 0-15 1- 2 | 3- 7 10-12 | 4-11 8-13 | 5-14 6- 9 3: 0-15 1- 2 | 3-10 7-12 | 4- 8 11-13 | 5-14 6- 9 4: 0-15 1- 2 | 3-10 7-12 | 4-13 5- 9 | 6- 8 11-14 5: 0-15 1- 2 | 3-12 8-11 | 4- 6 9-13 | 5-10 7-14 6: 0-15 1- 2 | 3-12 8-11 | 4- 9 6-13 | 5- 7 10-14 7: 0-15 1- 3 | 2-13 6- 7 | 4-11 9-12 | 5-10 8-14 8: 0-15 1- 4 | 2- 8 5-10 | 3-14 7- 9 | 6-13 11-12 9: 0-15 1- 4 | 2-11 5-12 | 3- 8 6-10 | 7- 9 13-14 10: 0-15 1- 4 | 2-12 9-10 | 3- 5 8-14 | 6-13 7-11 11: 0-15 1- 7 | 2-12 11-14 | 3-10 6- 8 | 4- 5 9-13 12: 0-15 1- 8 | 2- 3 12-14 | 4-13 6- 9 | 5-10 7-11 13: 0-15 1- 8 | 2- 4 13-14 | 3-12 7-10 | 5- 9 6-11 14: 0-15 1- 8 | 2-12 3-14 | 4-13 6- 9 | 5- 7 10-11 15: 0-15 1- 8 | 2-13 4-14 | 3-12 7-10 | 5- 6 9-11 16: 0-15 1- 8 | 2-14 4- 6 | 3- 9 12-13 | 5-10 7-11 17: 0-15 1- 8 | 2-14 10-12 | 3- 4 7-13 | 5- 9 6-11 18: 0-15 1-11 | 2- 3 5-12 | 4- 6 9-13 | 7-10 8-14 19: 0-15 1-11 | 2- 5 4-13 | 3- 7 10-12 | 6-14 8- 9 20: 0-15 1-11 | 2- 6 8-14 | 3- 4 7- 9 | 5-12 10-13 21: 0-15 1-11 | 2- 9 3-14 | 4-13 6- 7 | 5- 8 10-12 22: 0-15 1-12 | 2- 7 3- 9 | 4- 5 11-14 | 6-13 8-10 23: 0-15 1-12 | 2- 9 7-13 | 3- 4 5-10 | 6- 8 11-14 24: 0-15 1-12 | 2-11 8-13 | 3- 5 9-10 | 4- 7 6-14 25: 0-15 1-13 | 2- 8 6-11 | 3-14 9-10 | 4-12 5- 7 26: 0-15 2- 4 | 1- 7 6- 9 | 3- 8 11-12 | 5-13 10-14 27: 0-15 2- 4 | 1- 7 6- 9 | 3-11 8-12 | 5-10 13-14 28: 0-15 2- 4 | 1- 8 7-11 | 3-12 10-13 | 5- 6 9-14 29: 0-15 2- 4 | 1- 9 8-11 | 3- 7 6-12 | 5-10 13-14 30: 0-15 2- 4 | 1-11 7- 8 | 3-12 10-13 | 5- 9 6-14 31: 0-15 2- 4 | 1-12 7-13 | 3-10 8-11 | 5- 6 9-14 32: 0-15 2- 6 | 1-13 5-10 | 3- 9 7- 8 | 4-11 12-14 33: 0-15 2- 7 | 1- 3 12-13 | 4-10 8-11 | 5- 9 6-14 34: 0-15 2- 7 | 1-10 5- 9 | 3- 4 6-13 | 8-11 12-14 35: 0-15 2- 7 | 1-13 4-12 | 3-14 6- 8 | 5-11 9-10 36: 0-15 2- 7 | 1-13 5-14 | 3-11 8-12 | 4- 6 9-10 37: 0-15 2- 8 | 1- 4 5-10 | 3-14 6-13 | 7- 9 11-12 38: 0-15 2- 8 | 1- 6 5-12 | 3-14 11-13 | 4- 7 9-10 39: 0-15 2- 8 | 1-13 6-10 | 3- 5 4- 9 | 7-14 11-12 40: 0-15 2- 9 | 1- 5 11-12 | 3- 6 4-14 | 7-13 8-10 41: 0-15 2- 9 | 1-11 4- 7 | 3- 5 6-10 | 8-14 12-13 42: 0-15 2- 9 | 1-12 7-13 | 3- 4 11-14 | 5-10 6- 8 43: 0-15 2-11 | 1- 4 7-12 | 3- 5 6-13 | 8- 9 10-14 44: 0-15 2-14 | 1-12 5- 6 | 3-11 8-10 | 4- 9 7-13 45: 0-15 3- 4 | 1- 5 11-14 | 2-10 7- 9 | 6-12 8-13 46: 0-15 3- 4 | 1-12 5-10 | 2- 9 11-14 | 6- 8 7-13 47: 0-15 3- 4 | 1-13 9-11 | 2- 7 8-14 | 5-12 6-10 48: 0-15 3-11 | 1-14 9-12 | 2- 6 7- 8 | 4-13 5-10 49: 0-15 3-14 | 1- 4 7- 9 | 2- 8 6-13 | 5-10 11-12 50: 0-15 3-14 | 1- 4 10-11 | 2- 9 5- 7 | 6-12 8-13 51: 0-15 3-14 | 1- 9 8-11 | 2- 7 4-13 | 5- 6 10-12 52: 0-15 4- 7 | 1- 3 5-13 | 2- 8 9-14 | 6-10 11-12 53: 0-15 4- 8 | 1- 2 7-14 | 3-13 10-12 | 5-11 6- 9 54: 0-15 4- 8 | 1- 6 7- 9 | 2-14 3-12 | 5-13 10-11 55: 0-15 4- 8 | 1- 7 2- 3 | 5-10 11-13 | 6-14 9-12 56: 0-15 4- 8 | 1- 7 5- 6 | 2- 9 11-14 | 3-13 10-12 57: 0-15 4- 8 | 1- 9 6- 7 | 2-14 3-12 | 5-10 11-13 58: 0-15 4- 8 | 1-14 2- 7 | 3-10 12-13 | 5-11 6- 9 59: 0-15 4-12 | 1-14 3- 6 | 2-11 5-10 | 7- 8 9-13 60: 0-15 4-13 | 1- 5 6- 7 | 2- 9 10-12 | 3- 8 11-14 61: 0-15 4-14 | 1- 7 5- 8 | 2- 6 9-11 | 3-10 12-13 62: 0-15 4-14 | 1- 7 9-13 | 2- 5 3-10 | 6- 8 11-12 63: 0-15 4-14 | 1- 9 6- 7 | 2-11 10-13 | 3- 5 8-12 64: 0-15 4-14 | 1-12 6-13 | 2-11 8- 9 | 3- 5 7-10 65: 0-15 5-10 | 1- 2 4- 8 | 3-11 12-14 | 6- 9 7-13 66: 0-15 5-10 | 1- 2 4- 8 | 3-12 11-14 | 6-13 7- 9 67: 0-15 5-10 | 1- 3 4-12 | 2- 6 8- 9 | 7-13 11-14 68: 0-15 5-10 | 1- 3 4-12 | 2- 8 6- 9 | 7-11 13-14 69: 0-15 5-10 | 1- 4 2- 8 | 3-11 12-14 | 6- 7 9-13 70: 0-15 5-10 | 1- 4 2- 8 | 3-14 11-12 | 6-13 7- 9 71: 0-15 5-10 | 1- 4 3-12 | 2- 6 8- 9 | 7-14 11-13 72: 0-15 5-10 | 1- 4 3-12 | 2- 9 6- 8 | 7-11 13-14 73: 0-15 5-10 | 1- 8 2- 4 | 3-12 11-14 | 6- 7 9-13 74: 0-15 5-10 | 1- 8 2- 4 | 3-14 11-12 | 6- 9 7-13 75: 0-15 5-10 | 1-12 3- 4 | 2- 8 6- 9 | 7-14 11-13 76: 0-15 5-10 | 1-12 3- 4 | 2- 9 6- 8 | 7-13 11-14 77: 0-15 6- 7 | 1-14 4-12 | 2-13 3- 9 | 5-10 8-11 78: 0-15 6- 8 | 1-11 9-12 | 2-10 7-13 | 3-14 4- 5 79: 0-15 6- 8 | 1-12 11-14 | 2- 9 5-10 | 3- 4 7-13 80: 0-15 6- 8 | 1-13 4-14 | 2-11 3- 7 | 5-12 9-10 81: 0-15 6-13 | 1- 4 11-12 | 2- 8 3-14 | 5-10 7- 9 82: 0-15 6-13 | 1- 7 2- 3 | 4-14 8-11 | 5- 9 10-12 83: 0-15 6-13 | 1-11 9-12 | 2- 8 5- 7 | 3- 4 10-14 84: 0-15 7- 9 | 1- 4 3-14 | 2- 8 11-12 | 5-10 6-13 85: 0-15 7- 9 | 1-11 2-14 | 3-10 5- 6 | 4-13 8-12 86: 0-15 7- 9 | 1-12 10-11 | 2- 8 5-13 | 3- 6 4-14 87: 0-15 7-11 | 1- 4 6-13 | 2-12 3- 5 | 8-14 9-10 88: 0-15 7-11 | 1- 8 13-14 | 2-12 3- 5 | 4-10 6- 9 89: 0-15 7-11 | 1- 9 3- 6 | 2- 4 5-10 | 8-14 12-13 90: 0-15 7-11 | 1-13 3-12 | 2- 4 5-10 | 6-14 8- 9 91: 0-15 7-11 | 1-13 3-12 | 2-10 4- 5 | 6- 8 9-14 92: 0-15 7-11 | 1-14 8-13 | 2- 3 5-12 | 4-10 6- 9 93: 0-15 7-13 | 1- 8 3- 4 | 2-14 5- 9 | 6-11 10-12 94: 0-15 7-13 | 1-12 2- 4 | 3-10 9-14 | 5- 6 8-11 95: 0-15 7-13 | 1-12 2- 9 | 3- 4 6- 8 | 5-10 11-14 96: 0-15 7-14 | 1- 2 11-13 | 3-12 5- 8 | 4- 9 6-10 97: 0-15 7-14 | 1- 3 12-13 | 2-11 6- 9 | 4- 8 5-10 98: 0-15 7-14 | 1-11 2-13 | 3-12 5- 8 | 4- 6 9-10 99: 0-15 7-14 | 1-12 3-13 | 2-11 6- 9 | 4- 5 8-10 100: 0-15 7-14 | 1-13 3- 5 | 2- 8 11-12 | 4- 9 6-10 101: 0-15 7-14 | 1-13 9-11 | 2- 3 6-12 | 4- 8 5-10 102: 0-15 8- 9 | 1-14 3-11 | 2-13 6-12 | 4- 7 5-10 103: 0-15 8-11 | 1- 6 7-13 | 2-10 12-14 | 3- 4 5- 9 104: 0-15 8-13 | 1- 3 4- 7 | 2- 9 11-12 | 5-14 6-10 105: 0-15 8-13 | 1- 9 6-10 | 2- 3 12-14 | 4- 7 5-11 106: 0-15 8-13 | 1-10 2-14 | 3- 7 4-12 | 5- 6 9-11 107: 0-15 8-13 | 1-12 7- 9 | 2-14 3-11 | 4-10 5- 6 108: 0-15 8-14 | 1- 4 3-13 | 2- 6 10-11 | 5-12 7- 9 109: 0-15 9-13 | 1- 3 4-11 | 2-14 5-10 | 6-12 7- 8 110: 0-15 11-12 | 1- 4 6-13 | 2- 8 7- 9 | 3-14 5-10 111: 0-15 11-12 | 1- 4 10-14 | 2- 7 3- 9 | 5-13 6- 8 112: 0-15 11-12 | 1- 7 8-13 | 2-14 4- 6 | 3-10 5- 9 113: 0-15 11-13 | 1- 2 5-10 | 3- 7 4-12 | 6- 9 8-14 114: 0-15 11-13 | 1- 2 5-10 | 3- 9 8-12 | 4- 7 6-14 115: 0-15 11-13 | 1- 5 2-10 | 3- 4 7-12 | 6- 9 8-14 116: 0-15 11-13 | 1- 6 9-10 | 2- 5 3-12 | 4- 8 7-14 117: 0-15 11-13 | 1- 6 9-10 | 2- 8 3-14 | 4- 7 5-12 118: 0-15 11-13 | 1- 9 6-10 | 2- 5 3-12 | 4-14 7- 8 119: 0-15 11-14 | 1- 2 6- 8 | 3-10 4-13 | 5- 9 7-12 120: 0-15 11-14 | 1- 7 10-12 | 2- 9 4- 8 | 3-13 5- 6 121: 0-15 11-14 | 1-12 6- 8 | 2- 9 3- 4 | 5-10 7-13 122: 0-15 12-14 | 1- 7 5-10 | 2-13 8- 9 | 3- 6 4-11 123: 0-15 13-14 | 1- 4 7- 9 | 2-11 6-10 | 3- 8 5-12 124: 0-15 13-14 | 1- 5 8-10 | 2- 9 6-11 | 3-12 4- 7 125: 0-15 13-14 | 1- 8 5-10 | 2- 6 9-11 | 3-12 4- 7 126: 0-15 13-14 | 1- 8 5-10 | 2-11 3- 7 | 4- 6 9-12 127: 0-15 13-14 | 1-10 6- 9 | 2- 4 7-11 | 3- 8 5-12 128: 0-15 13-14 | 1-10 6- 9 | 2- 7 4-11 | 3- 5 8-12 NUMERO DI CALENDARI TESTATI: 14189175 Process returned 0 (0x0) execution time : 5.184 s
.
"sellacollesella":
Quindi, la domanda è ... ma tu ne trovi qualcuno in questa maniera oppure nada de nada?
Nada... ma ne parlo, insieme ad altre cose, nel mio precedente mapazzone!
.
"sellacollesella":
Ho provato a decifrare il tuo codice C++, ma è troppo tempo che non lo uso, non lo capisco! Non è che quando hai tempo, voglia, ecc ... potresti gentilmente spiegare come impostare i cicli iterativi? Grazie!
Certo, appena ho tempo cerco di spiegare come funziona la funzione [inline]giornata_0_successiva()[/inline].
P.S.
Ho fatto girare per qualche decina di secondi il programma impostando $N=20$, e qualche soluzione è saltata fuori!
"utente__medio":
In pratica, detto $ N $ il numero di squadre (indicate con i numeri che vanno da $ 0 $ a $ N-1 $), ricavo l'elenco delle sequenze associate alle "giornate 0" in cui alla prima partita si incontrano le squadre $ 0 $ e $ N-1 $. Una volta fissata la sequenza iniziale e una condizione di uscita, la definizione di ogni sequenza si basa esclusivamente sulla sequenza precedente sfruttando l'ordine delle partite.
Nel codice la funzione che se ne occupa è [inline]giornata_0_successiva()[/inline];
1) in relazione alla sequenza corrente (contenuta nell'array [inline]v[/inline] passato come argomento alla funzione), considero gli elementi a partire dal terzultimo a ritroso fino al terzo (i primi due elementi come già detto contengono rispettivamente $0$ e $N-1$);
2) controllo che l'elemento corrente non costituisca la prima squadra di una fascia oraria, o equivalentemente che il suo indice (che in un array parte da $0$) non sia un multiplo di $4$;
3) se il controllo 2) va a buon fine e l'elemento corrente ha indice dispari, controllo se tra gli elementi alla sua destra si trovi qualche elemento ad esso maggiore, e in tal caso prendo il minimo tra questi e li scambio di posto, e infine ordino in senso crescente gli elementi alla destra dell'elemento corrente;
4) se il controllo 2) va a buon fine e l'elemento corrente ha indice pari, controllo se tra gli elementi alla sua destra, escluso quello immediatamente successivo, si trovi qualche elemento ad esso maggiore, e in tal caso prendo il minimo tra questi e li scambio di posto, poi eventualmente scambio di posto l'elemento immediatamente successivo con l'elemento immediatamente maggiore all'appena modificato elemento corrente, e infine ordino in senso crescente i restanti elementi sulla destra;
- nella funzione [inline]giornata_0_successiva()[/inline], l'array [inline]u[/inline] è utilizzato per tenere traccia degli elementi considerati fino a quel momento.
Se qualcosa non è chiaro, fatemi sapere.
.
Di nulla, non preoccuparti!
Magari poi posto un esempio pratico che possa rendere le cose un po' più chiare.
Magari poi posto un esempio pratico che possa rendere le cose un po' più chiare.
"utente__medio":
1) in relazione alla sequenza corrente (contenuta nell'array [inline]v[/inline] passato come argomento alla funzione), considero gli elementi a partire dal terzultimo a ritroso fino al terzo (i primi due elementi come già detto contengono rispettivamente $ 0 $ e $ N-1 $);
2) controllo che l'elemento corrente non costituisca la prima squadra di una fascia oraria, o equivalentemente che il suo indice (che in un array parte da $ 0 $) non sia un multiplo di $ 4 $;
3) se il controllo 2) va a buon fine e l'elemento corrente ha indice dispari, controllo se tra gli elementi alla sua destra si trovi qualche elemento ad esso maggiore, e in tal caso prendo il minimo tra questi e li scambio di posto, e infine ordino in senso crescente gli elementi alla destra dell'elemento corrente;
4) se il controllo 2) va a buon fine e l'elemento corrente ha indice pari, controllo se tra gli elementi alla sua destra, escluso quello immediatamente successivo, si trovi qualche elemento ad esso maggiore, e in tal caso prendo il minimo tra questi e li scambio di posto, poi eventualmente scambio di posto l'elemento immediatamente successivo con l'elemento immediatamente maggiore all'appena modificato elemento corrente, e infine ordino in senso crescente i restanti elementi sulla destra;
- nella funzione [inline]giornata_0_successiva()[/inline], l'array [inline]u[/inline] è utilizzato per tenere traccia degli elementi considerati fino a quel momento.
Di seguito riporto qualche esempio per $N=8$.
Ho pensato un po' al problema e penso che il metodo più efficace dal punto di vista computazionale possa essere quello di fare uso di un algoritmo non deterministico. In particolare, si potrebbe partire da un calendario che non rispetti la condizione e poi fare delle trasformazioni al calendario che portano alla riduzione del numero massimo di volte che due squadre siano nella stessa fascia oraria. Scambiare due partite di una stessa giornata sembra una strategia semplice ma non credo sia sufficiente in base ad un test manuale che ho fatto. Un'alternativa è quella di spostare una partita da una giornata ad un altra ma questo porta ad una serie di cambiamenti a cascata. Ho iniziato a scrivere del codice per provarlo ma non è ancora pronto per essere condiviso. Ma forse avete qualche idea a riguardo.
"apatriarca":
Ma forse avete qualche idea a riguardo.
Qualche tentativo l'ho fatto pure io in tal senso, ma alla fine ho lasciato perdere perché non mi sembrava molto promettente come metodo, poi non so...
In ogni caso al momento mi sembra che l'approccio che ha dato i risultati migliori è quello descritto in questo mio precedente post; fino a $N=16$ squadre restituisce diverse soluzioni in modo modo molto rapido, per $N=20$ restituisce alcune soluzioni a distanza di qualche secondo tra l'una e l'altra, mentre per $N=24$ i tempi si dilatano e dopo alcuni minuti senza soluzioni ho lasciato perdere.
Con la funzione [inline]giornata_0_successiva()[/inline], come già detto, vado a generare ogni possibile giornata fissando le squadre $0$ e $N-1$ della prima partita (dove ipotizzo che due giornate distinte debbano essere indipendenti dall'ordine delle fasce orarie, dall'ordine delle partite all'interno delle singole fasce orarie e dall'ordine delle squadre all'interno delle singole partite), ma la generazione di ogni possibile calendario (dove due calendari distinti, oltre alle caratteristiche sopra menzionate per le giornate, devono essere anche indipendenti dall'ordine delle giornate stesse) è tutta un'altra questione, e proprio non saprei da dove iniziare.
Infine, relativamente ai metodi METODO_1 e METODO_2 (per la generazione di calendari a partire da una "giornata 0") menzionati nel post sopra linkato, avrei ancora un dubbio: partendo dalla seguente "giornata 0"
0-7 1-3 | 2-6 4-5
è possibile ricavare con METODO_2 lo stesso calendario che si ottiene con METODO_1? E nel caso come? Quale elemento andrebbe fissato?
Detto ciò, anche io ho messo tutte le carte sul tavolo e non saprei più cosa aggiungere!
Nonostante in questi giorni stia facendo un transloco e ho avuto poco tempo per fare altro, sono andato avanti nel mio esperimento. Facendo uso solo degli scambi non sono riuscito a passare da un calendario creato usando l'algoritmo circolare che si trova online per creare calendari ad uno che rispetti la condizione. Il meglio che ho ottenuto a partire dal calendario di costo 264
è stato qualcosa come il seguente con costo 26
Nota che gli indici delle squadre partono da 1. Il costo che ho usato è uguale alla somma dei quadrati del numero di volte che una coppia di squadre compare nella stessa fascia oraria meno due (il valore desiderato).
Il codice è il seguente.
1- 2 3-12 4-11 5-10 6- 9 7- 8 1- 3 2- 4 5-12 6-11 7-10 8- 9 1- 4 3- 5 2- 6 7-12 8-11 9-10 1- 5 4- 6 3- 7 2- 8 9-12 10-11 1- 6 5- 7 4- 8 3- 9 2-10 11-12 1- 7 6- 8 5- 9 4-10 3-11 2-12 1- 8 7- 9 6-10 5-11 4-12 2- 3 1- 9 8-10 7-11 6-12 2- 5 3- 4 1-10 9-11 8-12 2- 7 3- 6 4- 5 1-11 10-12 2- 9 3- 8 4- 7 5- 6 1-12 2-11 3-10 4- 9 5- 8 6- 7
è stato qualcosa come il seguente con costo 26
4- 7 1-11 3- 8 10-12 5- 6 2- 9 2- 7 9-11 8-12 1-10 3- 6 4- 5 1- 9 3- 4 8-10 7-11 6-12 2- 5 2- 3 1- 8 7- 9 4-12 6-10 5-11 2-12 3-11 6- 8 4-10 5- 9 1- 7 4- 8 5- 7 11-12 1- 6 2-10 3- 9 10-11 9-12 4- 6 2- 8 1- 5 3- 7 3- 5 8-11 7-12 2- 6 1- 4 9-10 7-10 2- 4 1- 3 6-11 5-12 8- 9 7- 8 6- 9 3-12 4-11 1- 2 5-10 6- 7 3-10 2-11 4- 9 1-12 5- 8
Nota che gli indici delle squadre partono da 1. Il costo che ho usato è uguale alla somma dei quadrati del numero di volte che una coppia di squadre compare nella stessa fascia oraria meno due (il valore desiderato).
Il codice è il seguente.
using Random, Distributions
const TEAMS_COUNT = 12
@assert TEAMS_COUNT > 0 && TEAMS_COUNT % 2 == 0
const MATCHES_IN_TURN = TEAMS_COUNT ÷ 2
const TURNS_COUNT = TEAMS_COUNT - 1
const TOTAL_MATCHES = MATCHES_IN_TURN * TURNS_COUNT
const MATCHES_IN_TIME_SLOTS = 2
@assert MATCHES_IN_TURN % MATCHES_IN_TIME_SLOTS == 0
const TIME_SLOTS_IN_TURN = MATCHES_IN_TURN ÷ MATCHES_IN_TIME_SLOTS
match(f, s) = f > s ? (s, f) : (f, s)
function create_calendar()
teams = [1:TEAMS_COUNT;]
calendar = fill((0, 0), (TURNS_COUNT, MATCHES_IN_TURN))
for turn in 1:TURNS_COUNT
teams[2:end] = circshift(teams[2:end], -1)
for i in 1:MATCHES_IN_TURN
calendar[turn, i] = match(teams[i], teams[TEAMS_COUNT-i+1])
end
end
return calendar
end
function compute_same_slot_relationship(calendar)
in_same_slot = Dict()
for i in 1:TEAMS_COUNT
for j in (i+1):TEAMS_COUNT
in_same_slot[i, j] = 0
end
end
for turn in 1:TURNS_COUNT
for time_slot in 0:(TIME_SLOTS_IN_TURN-1)
s = time_slot * MATCHES_IN_TIME_SLOTS
for i in 1:MATCHES_IN_TIME_SLOTS
for j in (i+1):MATCHES_IN_TIME_SLOTS
in_same_slot[match(calendar[turn, s+i][1], calendar[turn, s+j][1])] += 1
in_same_slot[match(calendar[turn, s+i][1], calendar[turn, s+j][2])] += 1
in_same_slot[match(calendar[turn, s+i][2], calendar[turn, s+j][1])] += 1
in_same_slot[match(calendar[turn, s+i][2], calendar[turn, s+j][2])] += 1
end
end
end
end
return in_same_slot
end
function compute_energy(calendar)
in_same_slot = compute_same_slot_relationship(calendar)
energy = 0.0
for (k, v) in in_same_slot
energy += (v - 2)^2
end
return energy
end
calendar = create_calendar()
display(calendar)
energy = compute_energy(calendar)
println("Old energy: ", energy)
turn_uniform_distribution = DiscreteUniform(1, TURNS_COUNT)
match_uniform_distribution = DiscreteUniform(1, MATCHES_IN_TURN)
other_time_slots_distribution = DiscreteUniform(1, MATCHES_IN_TURN - MATCHES_IN_TIME_SLOTS)
t = 100
a = 0.3
best_calendar = calendar
best_energy = energy
const K_MAX = 100000
for k in 1:K_MAX
# Random restart from best
if rand(Uniform(0, 1)) < min(1, energy / best_energy - 1)
calendar = best_calendar
energy = best_energy
end
# Choose random swap
turn = rand(turn_uniform_distribution)
i = rand(match_uniform_distribution)
time_slot_i = i ÷ MATCHES_IN_TIME_SLOTS
j = rand(other_time_slots_distribution)
if j >= time_slot_i * MATCHES_IN_TIME_SLOTS
j += MATCHES_IN_TIME_SLOTS
end
# Calendar and energy update
new_calendar = copy(calendar)
new_calendar[turn, i], new_calendar[turn, j] = new_calendar[turn, j], new_calendar[turn, i]
new_energy = compute_energy(new_calendar)
if new_energy < energy || rand(Uniform(0, 1)) < exp(-(new_energy - energy)/t)
global calendar = new_calendar
global energy = new_energy
if energy < best_energy
global best_energy = energy
global best_calendar = calendar
end
end
# Update temperature
global t = t / (1 + a*t)
end
println("Final energy: ", best_energy)
display(best_calendar)
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo