Newsgroup: it.comp.www.php
Titolo: Calendario torneo per N squadre

Salve a tutti,
ho un "nuovo" problema da sottoporre all'attenzione della corte! :p
Vorrei creare in PHP un calendario per un torneo aperto a n (pari)
squadre, che deve seguire queste regole:
- tutte le squadre disputano lo stesso numero di incontri
- ogni squadra incontra tutte le altre (n-1) squadre almeno una volta
durante ogni girone .
Affinchè tutte le squadre si incontrino servono (n-1) giornate.
Poichè le squadre sono in numero pari , il numero degli incontri da
disputare per ogni giornata è pari alla metà del numero delle squadre
(n/2) .
(non voglio essere prolisso, specifico tutto perchè dalla lettura dei
post precedenti ho dedotto che i dettagli sono importanti per valutare
il problema)
Ho proceduto così:
- Infilo in un array ($squadre) i nomi delle n squadre (sempre in
numero pari).
- prendo il primo elemento dell'array e lo combino con gli altri (n-1)
elementi.
- elimino quell'elemento dall'array
- con un ciclo questa procedura viene reiterata finche l'array $squadre
non è vuoto.
Fin qui OK, ottengo tutte le combinazioni a gruppi di 2 delle n squadre
e le infilo in un nuovo array che io ho chiamato $partite..
A questo punto, il nocciolo della questione è assegnare ogni
combinazione $partite[$x] in una matrice/tabellone del tipo
$INCONTRI[giornata][partita]
Con dei cicli for annidati genero la matrice e, per ogni incontro ,
scandisco gli elementi di $partite in modo da inserire in ogni incontro
la prima combinazione valida  che trovo.
Esempio: se ho 6 squadre (A, B, C, D, E, F)
[Prima giornata]
la prima combinazione della prima giornata sarà AB;
questo esclude che nella prima giornata ci siano altri incontri delle
squadre A e B;
stesso discorso per la combinazione CD, vengono escluse tutte le altre
combinazioni di C e tutte le combinazioni di D. E infine  viene
inserita la combinazione EF.
le combinazioni (AB, CD, EF) inserite nella matrice/tabellone vengono
eliminate dall'array partite.
[Seconda giornata]
La prima combinazione valida è AC (che esclude ogni altra combinazione
di A e di C), poi con la stessa procedura trova BD.
A questo punto nasce l'intoppo!
La combinazione EF è stata inserita nella prima giornata ed eliminata.
Le altre combinazioni di E e di F non sono valide, perchè sono
composte con A,B,C,D e vengono scartate dallo script.
Andando avanti con questo metodo, rimangono degli spazi vuoti nel
tabellone , mentre l'array partite non viene svuotato, poichè in esso
restano gli scarti non ammissibili nel tabellone per incoerenza (non è
possibile far giocare due o più partite alla stessa squadra nella
stessa giornata).
Per cui non è neanche possibile scandire la matrice
$INCONTRI[giornata][partita] per inserire gli scarti nel tabellone: non
esistono posizioni possibili.
Ho cercato di rimediare alla situazione mescolando l'array $partite con
shuffle(), in modo che l'estrazione casuale della prima combinazione
valida favorisse la sistemazione del tabellone. e devo dire che la
situazione migliora, ma di poco!!
A parità di numero di squadre (diciamo 6), con un array "ordinato"
(AB, AC, AD AE... EF)
ottengo sempre 11 scarti.
Se mescolo l'array ottengo un numero di scarti variabile, ma comunque
inferiore a 11 nella quasi totalità dei casi.
E adesso, la domanda cruciale:
Esiste un altro metodo? E se sì, qualcuno potrebbe cortesemente
suggerirmelo?
Io non ne vengo a capo, tutte le volte che intravedo una soluzione,
questa mi sfugge! :s
Mi affido a voi! :D
per completezza vi allego anche il codice commentato, magari può
tornare utile a qualcuno!
Scusate se mi son dilungato e
Grazie a tutti!! CIAO!
H
### CODICE ###
<style>
body {font-family:monospace;}
</style>
<?
$squadre = array( 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'L',
'M', 'N');
//$squadre = array( 'A', 'B', 'C', 'D', 'E', 'F');
$n_squadre = count($squadre); # numero delle squadre
$n_giornate = $n_squadre -1;  # numero giornate del girone
$partite_g = $n_squadre /2;   # numero partite del girone
#----------------------------------#
# Ciclo che genera le combinazioni #
#----------------------------------#
for ($i = $n_squadre; $i>0; $i--)
{
// debug
//print_r($squadre);
# registra il primo elemento dell'array $squadre nell'array
$current
# e lo elimina dall'array $squadre
$current = array_shift($squadre);
# $tmp tiene conto del decremento di squadre a ogni giro del ciclo
$tmp = count($squadre);
# ciclo che associa a ogni elemento n dell'array $squadre
# ai restanti (n-1) elementi
for ($j=0; $j< $tmp; $j++)
{
echo ($x+1).") $current[0] - $squadre[$j] <br> \n";
$partite[$x] = array( casa => $current[0] , fuori =>
$squadre[$j]);
$x++;
}
}
## Fine ciclo ##
# creo un array vuoto per il controllo delle combinazioni valide
$lista = array();
# rendo casuale l'ordine degli elementi di $partite
shuffle($partite);
$x=0;
#-----------------------------------------------#
# Serie di cicli che associano una combinazione #
# di squadre a ogni partita del torneo          #
#-----------------------------------------------#
for ($g=1; $g <= $n_giornate; $g++)
{
for ($i=1; $i < $partite_g; $i++)
{
$count = count($partite);
shuffle($partite);
//sort($partite);
for ($x=0; $x < $count ; $x++)
{
# se nessuno dei due elementi della combinazione $x
# è presente nell'array $lista la combinazione è valida
if (    !in_array($partite[$x][casa] , $lista)
&& !in_array($partite[$x][fuori], $lista)
)
{
# la combinazione viene assegnata all'array $giornata
$giornata[$g][$i][casa] = $partite[$x][casa];
$giornata[$g][$i][fuori] = $partite[$x][fuori];
# in caso di assegnazione la variabile $i viene
incrementata
$i++;
#la combinazione valida viene inserita nella lista di
controllo
array_push($lista, $partite[$x][casa],
$partite[$x][fuori]);
// elimino la combinazione valida dall'array partite
unset($partite[$x]);
}    # END if
}  # END for ($x)
}  # END for ($i)
unset($lista);    # distrugge l'array $lista alla fine di ogni
giornata
$lista = array(); # e lo ricrea per il prossimo giro del ciclo
//$i=1;
}   # END for ($g)
// debug
// print_r($lista);
# stampo gli array $giornata e $partite per verifica
echo "Giornata: <br>" ;
print_r($giornata);
echo '<hr> partite: <br>';
print_r($partite);
echo '<hr> Combinazioni non assegnate: <b>'. count($partite). '</b>';
?>

Io imposterei in un altro modo il problema:
C'č uno schema facile facile per i gironi all'italiana
Prima ipotesi: numero di squadre dispari (esempio: nove squadre):
Prima giornata: le dispongo cosě, in senso antiorario
1-9
2-8
3-7
4-5
5 riposa
Seconda giornata
6-5
7-4
8-3
9-2
1 riposa
E cosě via, sempre facendo riposare quella che era la prima squadra e
scrivendo numeri in senso antiorario
Seconda ipotesi: numero pari (esempio 10)
Uso lo stesso schema delle nove squadre; la squadra che avrebbe dovuto
riposare gioca contro la 10 (naturalmente alternando casa e fuori se c'č
anche il ritorno)
Ciao

 Ciao
Ciao ,
ho provato a sviluppare il tuo metodo con carta e penna, ma non mi
tornano i conti.
Con 8 squadre dovrebbero bastare 7 giornate, , ma mi viene fuori
Giornate  1° |  2° |  3° |  4° |  5° |  6° |  7° |
-------------|-----|-----|-----|-----|-----|-----| 
         1-8 | 8-7 | 7-6 | 6-5 | 5-4 | 4-3 | 3-2 | 
         2-7 | 1-6 | 8-5 | 7-4 | 6-3 | 5-2 | 4-1 | 
         3-6 | 2-5 | 1-4 | 8-3 | 7-2 | 6-1 | 5-8 |  
         4-5 | 3-4 | 2-3 | 1-2 | 8-1 | 7-8 | 6-7 |
ho tralasciato di alternare perchè volevo provare le combinazioni, ma
in questo modo gli incontri vengono ripetuti dopo la giornata (n/2)+1,
infatti la 5° sarebbe il "ritorno" della 1°, la 6° il ritorno della
seconda... ecc ecc
Sicuramente sto interpretando male io, ma non vedo altro modo per
scrivere i numeri in senso antiorario...
lo so: sono di coccio! ti chiedo una cortesia infinita: mi
svilupperesti il tuo metodo nel modo corretto?
Thanks!!
H

> svilupperesti il tuo metodo nel modo corretto?
   1° |  2° |  3° |  4° |  5° |  6° |  7° |
-----|-----|-----|-----|-----|-----|-----|
 1-7 | 5-4 | 2-1 | 6-5 | 3-2 | 7-6 | 4-3 |
 2-6 | 6-3 | 3-7 | 7-4 | 4-1 | 1-5 | 5-2 |
 3-5 | 7-2 | 4-6 | 1-3 | 5-7 | 2-4 | 6-1 |
 4-8 | 8-1 | 5-8 | 8-2 | 6-8 | 8-3 | 7-8 |
Squadre pari: si fa lo schema come per il torneo a 7 e poi si mette l'8 a
giocare contro quella che invece riposerebbe.
Se vuoi, ti mando lo schema per tutte le squadre che vuoi. Un secolo fa feci
un programmino in basic che lo generava.
Saluti.
Stefano Drei Liceo Torricelli