[Java] Generazione calendario squadre

[simoneRDZN]

Ciao,
sto sviluppando un applicazione che generi, dato un numero di squadre, un calendario accoppiando in maniera random le varie squadre in modo da evitare ovviamente ripetizioni sia nelle singole giornate che nell'intero girone.

Il problema è questo:
vorrei evitare di utilizzare le teorie delle permutazioni (quindi tanta matematica!!) per i vari accoppiamenti cercando di semplificare il tutto all'utilizzo di vettori, mappe, e opportuni controlli di cui sopra...
In questo caso xò non sempre ottengo un calendario senza ripetizioni, e per ovviare a ciò ho pensato di usare la ricorsività del metodo, in modo che, per il calcolo delle probabilità, prima o poi dovrebbe venire....ma non mi sembra la soluzione ottimale, e cmq capita che generi eccezioni del tipo "java.lang.StackOverflowError"...

Avete dei consigli???

[Andrea1979]

Studia matematica e le permutazioni in particolare.

[simoneRDZN]

se qualcuno avesse dei consigli a livello di codice sarebbe molto ben accetto...

[redcloud]

Guarda, per come la vedo puoi risolvere cone le permutazioni. Se non ti va di studiare la matematica, trova un algoritmo in pseudo linguaggio sulle permutazioni e adattalo al tuo codice.

[simo7784]

Ciao, ho trovato qualcosa che forse potrebbe interessarti.
Anche perche' il problema non migliora usando le permotazioni se non hai in testa un buon algoritmo.
Un consiglio: in questo caso evita la ricorsione se possibile (che al 90% era la causa del tuo java.lang.StackOverflowError).

Sono un appassionato di informatica. Qual è l'algoritmo per calcolare in un campionato di N squadre gli accoppiamenti di dette squadre, a 2 a 2, per tutte le N-1 giornate?

(Risponde Carlo Consoli)
L'algoritmo per calcolare gli n/2 accoppiamenti di tutte le n(n-1)/2 del girone di andata di un campionato di n squadre, per le n-1 giornate è il seguente, ed è valido solo per n pari.

per ogni giornata g che va da 1 a n-1
   per ogni partita i che va da 1 a n/2
      la partita i è giocata da una qualsiasi coppia di squadre tali che:
         1) non hanno mai giocato tra di loro in qualsiasi giornata
         2) le restanti squadre che non sono state ancora selezionate per giocare nella giornata attuale non hanno mai giocato tra di loro nelle giornate precedenti

Ad esempio, in un campionato di 6 squadre, ABCDEF, l'algoritmo procede come segue: Giornata 1 A-B C-D E-F Giornata 2 A-C L'accoppiata B-D non è possibile perché lascerebbe le squadre E-F che hanno già giocato nella giornata precedente, quindi: B-E D-F e così via per le restanti giornate.

Io non l'ho provato per mancanza di tempo.
Se funziona parti da qui, poi magari estendilo ad n sia pari che dispari.
In bocca al lupo per il programma.

[simoneRDZN]

ciao simo7784,
il mio algoritmo è il seguente ed è molto simile a quello da te citato:
date n squadre,
ciclo per n-1 giornate

[simoneRDZN]

ciao simo7784,
il mio algoritmo è il seguente ed è molto simile a quello da te citato:

date n squadre,
ciclo per n-1 giornate
{
ciclo per n/2 partite
{
- prendo e rimuovo (random) dal vettore "squadre" la squadra in casa;
- prendo la squadra in trasferta:
- se è la prima giornata le accoppio;
- dalla seconda giornata in poi controllo prima che non abbiano già giocato: in caso
positivo (hanno già giocato contro) passo alla squadra successiva e rifaccio tutti
i miei controlli; in caso negativo (ancora non si sono incontrate) le accoppio e
rimuovo anche la squadra in trasferta dal vettore "squadre";
(ovviamente il vettore "squadre" viene clonato, per ogni giornata, da un altro vettore passato in input al metodo, che contiene tutte le squadre del campionato)
ogni volta che faccio un nuovo accoppiamento:
- riempio un Hashtable, creata in precedenza, che assocerà ad ogni squadra
(la key) un vettore contenente tutte le squadre affrontate. E' su questa
Hashtable che vado a fare il controllo di cui sopra;
- inserisco la partita in un vettore "giornata" che conterrà tutte le partite
della singola giornata;
}
aggiungo al vettore "girone" il vettore "giornata";
}

Il problema è che non sempre va tutto a buon fine e può verificarsi che in una giornata siano finiti i possibili accoppiamenti da fare e che quindi due squadre possano affrontarsi per una seconda volta nel girone.
La ricorsione era soltanto per riuscire ad ottenere il calendario esatto, che per il calcolo delle probabilità prima o poi deve uscire fuori (e in effetti è così, a volte ottengo il calendario correttamente riempito) ma in questo modo mi va in eccezione (StackOverflowError) .

[simo7784]

Credo che il problema risieda nel fatto che il tuo algoritmo non rispetta il vincolo 2) di quello che ho trovato io online.

[Andrea1979]

Cambia sistema di gestione:

-Usa un Vector o altra struttura analoga per contenere tutte le possibili partite.

Per creare la giornata:
-Crea un altro Vector (o simile) per la prima giornata del campionato come copia della struttura dati che contiene la lista di tutte le possibili partite.

-Scegli una partita a caso (va bene anche la prima per mantenere le cose semplici) e la cancelli dalla struttura dati di tutte le partite possibili e cancelli dalla struttura dati della giornata tutte le partite che non si possono effettuare (ossia tutte quelle dove compaiono le due squadre)
-Da questa lista menomata scegli ancora una partita a caso, la elimini dalla lista di tutte le partite possibili ed elimini tutte le partite impossibili dalla lista della giornata. Continui così fin quando la lista della giornata a vuota (mentre la lista delle partite possibili sarà stata ridotta di n/2 elementi).

Ripeti il procedimento fino a quando la struttura dati di tutte le partite possibili è vuota (ossia hai creato tutte le giornate del girone).


Complicazione 1)
Se le squadre sono dispari, aggiungi una squadra fittizia "Riposo" e crei la giornata alla stessa maniera: la squadra che gioca contro Riposo è la squadra che avrà la giornata di riposo

Complicazione 2)
Casa/Trasferta: invece di scegliere in modo pseudo-random le partite di una giornata, crei una lista di priorità assegnando priorità maggiore a chi ha giocato in trasferta nella giornata precedente e a parità di priorità a chi ha giocato complessivamente più partite in trasferta. Scegli chi gioca in casa in base alla coda di priorità ogniqualvolta sia possibile.

[simo7784]

Ma cosi' il problema rimane. Faccio un esempio pratico: 6 Squadre (A, B, C, D, E, F).

Giornata 1
Partite possibili: [A-B,A-C,A-D,A-E,A-F,B-C,B-D,B-E,B-F,C-D,C-E,C-F,D-E,D-F,E-F]
partita scelta: A-B rimangono: [C-D,C-E,C-F,D-E,D-F,E-F]
partita scelta: C-F rimangono: [D-E]
partita scelta: D-E rimangono: [] OK!
Giornata 2
Partite possibili: [A-C,A-D,A-E,A-F,B-C,B-D,B-E,B-F,C-D,C-E,D-F,E-F]
partita scelta: A-D rimangono: [B-C,B-E,B-F,C-E,C-F,E-F]
partita scelta: B-F rimangono: [C-E]
partita scelta: C-E rimangono: [] OK!
Giornata 3
Partite possibili: [A-C,A-E,A-F,B-C,B-D,B-E,C-D,D-F,E-F]
partita scelta: A-E rimangono: [B-C,B-D,B-F,C-D,C-F,D-F]
partita scelta: B-C rimangono: [D-F]
partita scelta: D-F rimangono: [] OK!
Giornata 4
Partite possibili: [A-E,A-F,B-C,B-D,C-D,D-F,E-F]
partita scelta: A-C rimangono: [B-D,B-E,B-F,D-E,D-F,E-F]
partita scelta: B-E rimangono: [D-F] !!!! D-F è già stata giocata ma mi rimane solo quella da scegliere

Credo che non violi il tuo algoritmo andrea, però non funziona alla perfezione. (Stavo facendo le prove con un algoritmo simile e mi dava lo stesso problema). Se mi sbaglio, chiedo venia.