Help Calendario Campionato con Algoritmo di Berger

[ricman]

Volevo creare uno script che mi calcoli le giornate per costruire un calendario partite di un campionato.
Trovo dovunque che l'Algoritmo di Berger fa al caso mio.
Lo provo, ad esempio, su 8 squadre (quindi ogni squadra giocherà 3 partite in casa e 4 fuori o viceversa) MA una mi gioca troppe partite in casa...
L'algoritmo (una funzione) l'ho presa da wikipedia e come array di squadre in ingresso ho dato:
$arrSquadre = array('111','222','333','444','555','666','777','8 88');

Come risultato ho ottenuto questo (Controllate la squadra 555):

1a Giornata
888 - 111
777 - 222
666 - 333
555 - 444

2a Giornata
111 - 222
333 - 888
444 - 777
555 - 666

3a Giornata
333 - 111
222 - 444
888 - 555
777 - 666

4a Giornata
111 - 444
555 - 333
666 - 222
777 - 888

5a Giornata
555 - 111
444 - 666
333 - 777
222 - 888

6a Giornata
111 - 666
777 - 555
888 - 444
222 - 333

7a Giornata
777 - 111
666 - 888
555 - 222
444 - 333

[Alhazred]

E quindi la domanda è?

[Santino83_02]

che aiuto vuoi? dato per scontato che quello script su wikipedia sia ben fatto, diamo per buono il risultato. Se il risultato non va bene le cose sono quattro:

- hai sbagliato qualcosa te
- è sbagliata l'implementazione dell'algoritmo ( ad esempio prova a vedere se la versione javascript da lo stesso risultato)
- è sbagliato l'algoritmo (dubito)
- quello è il risultato corretto

vedi un pò te

[Alhazred]

Tra l'altro l'ho provato, genera sempre lo stesso tabellone e anche la squadra 777 gioca 5 partite in casa e 2 fuori come la 555.

[Infocurci]

Ma a cosa ti serve? se ti serve una cosa una-tantum ti conviene prendere un calendario già fatto da qualche competizione sportiva e associare le tue squadre a quelle di quel calendario.. io di solito faccio cosi.
ad esempio, se ti servono 8 squadre, c'è il campionato di baseball che parte oggi che ne ha proprio 8, puoi usare quello.

[ricman]

Tra l'altro l'ho provato, genera sempre lo stesso tabellone e anche la squadra 777 gioca 5 partite in casa e 2 fuori come la 555.

La domanda quindi era: è normale un comportamento simile?

Quale squadra vorrebbe giocare 5 partite fuori casa e 2 in casa??
Su 7 partite posso capire la suddivisione in 3 fuori e 4 in casa (o viceversa) ma 5-2 mi pare un rapporto non accettabile...

Conoscete qualche altro script migliore di questo?

[ricman]

che aiuto vuoi?

Beh... io fatto copia/incolla e ho solo inviato 8 squadre alla funzione... Quindi è regolare che QUEL codice dia quel risultato...

Quindi forse ci vuole un altro script, forse questo algoritmo non si adatta bene ad un campionato... Non so che dire...

Conosci qualche altro script che faccia tale cosa?

[Alhazred]

Se su 7 partite se ne devono avere 4 in casa e 3 fuori o viceversa, l'implementazione dell'algoritmo è chiaramente sbagliata, anche la versione JS ha lo stesso problema, quella Java non l'ho provata, ma suppongo dia lo stesso risultato.

Alternative già pronte non ne conosco, se non se ne trovano puoi sempre crearti uno script tuo, non starti a preoccupare di ottimizzazione, tanto il numero di squadre non sarà mai tanto alto da farti notare differenze di prestazione tra un algoritmo scritto coi piedi (purché funzionante) e uno iper-ottimizzato.

[ricman]

Hai qualche idea? ...io già ho difficoltà a capire fino in fondo le ultime manovre sugli dello script dell'algoritmo di berger.
Riguardo ai tornei non credo che mai si superi le 32 squadre (la media è 12 squadre, ma per eventi cittadini particolari ho raggiunto anche le 24 squadre)

[clasku]

il problema risiede nella parte finale della funzione

        // Ruota in gli elementi delle liste, tenendo fisso il primo elemento
        // Salva l'elemento fisso
        $pivot = $casa[0];
         /* sposta in avanti gli elementi di "trasferta" inserendo
            all'inizio l'elemento casa[1] e salva l'elemento uscente in "riporto" */ 
       array_unshift($trasferta, $casa[1]);        $riporto = array_pop($trasferta);
         /* sposta a sinistra gli elementi di "casa" inserendo all'ultimo            posto l'elemento "riporto" */
       array_shift($casa);
        array_push($casa, $riporto);
         // ripristina l'elemento fisso
        $casa[0] = $pivot; 

bisogna trovare il modo per evitare che queste operazioni sugli array portino l'ultima squadra a fare più trasferte di altre (potete verificarlo facendo un sort su trasferte, quella con più trasferte diventa 888)