Calcolo tabella incontri di un girone unico di un torneo

[ricman]

Supponiamo di avere 10 o 12 squadre che partecipano ad un torneo.

La formula del torneo è semplice: in un giorno si gioca tutti contro tutti a seguire... da mattina a sera..

Il mio obiettivo sarebbe quello di non far mai giocare ad una squadra due partite consecutive (anzi, essendo sport, più lontano gioco dall'ultima partita meglio è).

Che calcoli si fanno in questi casi?

[Grino]

Mi ci è voluto un po', ma alla fine ho elaborato una possibile soluzione

http://fruttodigitale.altervista.org/Incontri/

Buon divertimento!

[ricman]

ehemm... Si vede solo il risultato (che mi pare funzioni)... però non ci hai spiegato nulla ... nè mostrato un po' di codice.

[Grino]

La cosa si è svolta così:

Ho perso un paio di ore a cercare di trovare un metodo (a manina, quindi con un bel foglio e una matita) per stabilire l'ordine degli incontri.

La prima cosa che mi è venuta in mente è stata quella di stabilire quali debbano essere le partite da giocare affinchè tutti giochino con tutti. Supponendo 6 squadre (da 1 a 6) gli incontri saranno

12 13 14 15 16 23 24 25 26 34 35 36 45 46 56

sono quindi due cicli annidati in cui il primo indice va da 1 a n-1 e il secondo va dal primo indice +1 fino ad n

Ed hai così l'elenco delle partite da giocare. Ho quindi cercato di stabilire un ordine partendo da questo elenco ma non ci sono riuscito. Quindi mi sono detto. E' ovvio avviare le partite nell'rodine in cui si presentano le squadre:
12 34 56

L'elenco delle partite da giocare diventa
13 14 15 16 23 24 25 26 35 36 45 46

La squadra più riposata è la 1 ma con chi farla giocare? la 2 ma la partita non è più disponibile. La 3? sì
Partite giocate 12 34 56 13
Partite da giocare 14 15 16 23 24 25 26 35 36 45 46

Ora la più ripostata è la 2 ma con chi gioca? La 3 ha appena giocato quindi la 4 e dato che la partita 24 è ancora da giocare
12 34 56 13 24
14 15 16 23 25 26 35 36 45 46

Ora tocca alla 5 ma con chi? Con la 6 ha giocato, ma con la 1 no ed essendo la partita disponibile
12 34 56 13 24 15
14 16 23 25 26 35 36 45 46

Ora la più riposata è la 6 ma con chi farla giocare? La più riposata è la 3 e la partita 36 non è ancora stata giocata e via
12 34 56 12 13 24 15 36
14 16 23 25 26 35 45 46

E vai avanti così finchè le partite da giocare non sono finite.

Quindi hai un ciclo principale che termina quando hai svuotato il contenitore delle partite da giocare e dentro questo un metodo (ciclo) per individuare la squadra più riposata quindi stabilire una seconda squadra, da quella più riposata a quella meno, con la quale la partita non sia stata giocata. Se individui la partita rimuovi questa partita dal contenitore delle partite e la aggiungi a quelle da giocare e ripeti il processo. Se non individui la partita, perchè evidentemente la prima squadra ha giocato tutte le sue partite, allora prendi come prima squadra la seconda più riposata e cerchi una seconda squadra con cui farla giocare.

Alla fine avrai popolato il contenitore delle partite giocate che ti da la sequenza e svuotato il contenitore della partite da giocare

Questo è l'algoritmo che sono riuscito ad individuare applicato nella paginetta che ti ho linkato. Di sicuro non è il migliore possibile ma è una prima soluzione.

[ricman]

Sto leggendo (e rileggendo!!) il tuo post per vedere se imparo qualcosa. Il ragionamento mi pare corretto e gli incontri, da quello che dici, vengono posti con la giusta cadenza.
Non riesco però a tradurre in codice il tutto. Ad esempio i due cicli annidati io li ho interpretati così:

$n=6;
for($a=1; $a<=$n-1; $a++)
{
    echo "A$a ";
    for($b=$a+1; $b<=$n; $b++)
    {
        echo "B$b ";
    }
    echo "
";
} 

...ma non mi pare dia il risultato giusto come dicevi tu. O meglio dalla stampa a video, se si contano, si trovano 15 incontri (giustamente) ma solo se li conto si fa "col dito" (la colona A contro ogni B)

[albx87]

Ciao, prova a vedere l'algoritmo di berger (http://it.wikipedia.org/wiki/Algoritmo_di_Berger), è usato proprio per questo tipo di problematiche,

[Grino]

Fin qui hai solo individuato quali sono le partite da giocare non l'ordine in cui giocarle.
Le squadre hanno come nome un indice numerico. La partita 1-2 (12) è equivalente alla 2-1 (21) ossia dovendosi incontrare le due squadre una sola volta le due notazioni sono equivalenti.
il sistema dei due cicli annidati ti prende sempre quella con indice minore in prima posizione e scarta quelle che prevedono un indice maggiore del secondo in prima posizione (6 squadre):

12 23 34 45 56
13 24 35 45
14 25 36
15 26
16

Se ho già la 34 è inutile calcolare la 43 perchè sono equivalenti nel significato.

definito questo elenco inizi a selezionare la partite secondo l'ordine attesso.

Le prime partite le conosci sempre: 10 squadre?
0123456789
le partite ordinate saranno
0-1;2-3;4-5;6-7;8-9;
e le rimuovi dall'elenco delle partite da giocare che hai creato all'inizio.

Inizi il ciclo di calcolo per le partite successive individuando la squadra più riposata (0), la seconda più riposata e se la partita è da giocare (1 ma 0-1 è stata giocata 2 e 1-2 non è stata giocata - ancora presente nell'elenco che hai creato con i cicli annidati - quindi è questa la prossima partita [attenzione se estrai 5-1 lo devi cambiare in 1-5 che è presente fra le partite da giocare]) la estrai (rimuovi fiscamente) dalle partite da giocare e la aggiungi in coda alle partite ordinate. Se non individui una partita vuol dire che la prima squadra più riposata presa in considerazione ha giocato tutte le sue partite, quindi non giocherà più.

Così popoli le partite nell'ordine di gioco, estraendole da quelle che devono essere giocate. Quando l'elenco delle partite che devono essere giocate è vuoto (condizione di fine ciclo di calcolo), hai tutte le partite nell'ordine atteso nell'altro elenco (quello che abbiamo chiamato elenco della partite ordinate - quello in cui agigungevi le partite).

Il metodi con cui tradurre questo in codice sono molteplici... a furia di parlarne ne ho immaginati altri 3 più efficienti di quello realizzato.

Posso essere unpo' impiccione? Ma a che ti serve sta roba?

[ricman]

Originariamente inviato da albx87
Ciao, prova a vedere l'algoritmo di berger (http://it.wikipedia.org/wiki/Algoritmo_di_Berger), è usato proprio per questo tipo di problematiche,

L'avevo già trovato, però vedo che quell'algoritmo si preoccupa di dividere in Giornate, gestire chi gioca in casa e chi no, e funziona solo con numero pari di squadre.

Io invece volevo fare tutti contro tutti, una partita dietro l'altra..

[ricman]

Originariamente inviato da Grino
Posso essere unpo' impiccione? Ma a che ti serve sta roba?

Organizzo per un oratorio dei tornei estivi (per beneficenza) e vorrei farmi un sitarello da tenere come punto di riferimento. Essendo tornei in cui giocano ragazzi (che sono sempre collegati a internet) è molto carino che vedano le classifiche sempre aggiornate o le foto etc..
Ho già preparato tutta la parte relativa agli eventi, alle iscrizioni squadre e alla classifica (php/mysql). Mi tornerebbe mooolto comodo poter combinare gli incontri in automatico una volta chiuse le iscrizioni, così non devo ammattire su carta... ma sono un po limitato con la programmazione pura e non riesco ad approcciare così in profondità al php

Ora provo ad unire le tue spiegazioni e vedere se ne tiro fuori le gambe.
(nel frattempo ti ringrazio, le tue spiegazioni sono sempre molto chiare)

[Grino]

Vai al link
http://lavorielavoretti.blogspot.it/...oni-senza.html

meglio di così non lo posso spiegare. Lì trovi anche un link ad una nuova demo che ti permette anche di visualizzare tutto il codice sorgente.

Ricordati di me nelle tue preghiere. E se ti scappa un grazie a me misero nel tuo portaletto... la cosa mi fa molto piacere.