Lavori e Lavoretti: Calcolo delle competizioni senza ripetizioni con massimo riposo (Parte1/2)

Curiosando su un forum mi è capitato d'imbattermi in un quesito simpatico (demo soluzione con codice visionabile). Si chiedeva come calcolare l'ordine degli incontri/partite giocate su un solo campo e in una sola giornata permettendo alle squadre/concorrenti di riposare il più possibile tra un incontro e l'altro.

Non conoscendo una soluzione, ho pensato bene di prendere carta e matita e iniziare a cercare un metodo manuale per risolvere il problema. Ho quindi stilato l'elenco degli incontri necessari nel caso di 6 squadre ottenendo:

Elenco di tutte le possibili partite a 6 squadre

L'algoritmo per ottenere questo elenco è semplice. Si tratta di due cicli annidati in cui il primo indice parte da 1 e finisce a n-1 (con n numero di squadre) ed il secondo va dal primo indice+1 fino ad n.

Dopo vario pensare sul come ordinare questi valori per ottenere il risultato, sono arrivato alla conclusione che occorreva stabilire l'ordine di chiamata in campo delle squadre (che chiamo sequenza). La cosa più naturale all'inizio è chiamare le squadre in ordine, ossia dalla 1 alla 6 (sempre esempio con 6 squadre).

Punto di Inizio


Sequenza di chiamata in campo	Elenco delle partite aggiornato

Sequenza è un array che mi dice in che ordine chiamare le squadre in campo. Se letto due valori alla volta restituisce i primi 3 incontri. Occorre però aggiornare l'elenco delle partite previste rimuovendo quelle giocate (segnate in rosso).

Ora che sequenza e partite sono inizializzati, possiamo procedere calcolando ciclicamente le nuove chiamate in campo fino all'esaurimento delle partite da giocare. Essendo la squadra più riposata la 1 (in cima alla sequenza), è lei certamente a dover giocare, ma con chi? Con la 2, seconda più riposata no, perchè la partita 1-2 è già stata giocata. Con la 3? Si, perché la partita 1-3 è ancora da giocare. Quindi aggiorno la sequenza aggiungendo in fondo 1 e 3. Segno come utilizzati gli elementi 1 e 3, in cima alla sequenza al fine di non riutilizzarli per errore, e cancello la partita dall'elenco delle partite. La situazione aggiornata è:


Sequenza di chiamata in campo	Elenco delle partite aggiornato

Ora la più riposata è la 2, ma con chi farla giocare? La 4, seconda squadra più riposata? Essendo disponibile la partita 2-4, questa è la partita successiva:


Sequenza di chiamata in campo	Elenco delle partite aggiornato

Ora tocca alla 5 (primo quadratino bianco in sequenza) ma con chi? La 6 no perchè 5-6 è già giocata. La 1? C'è la 5-1, equivalente alla 1-5, da giocare. Ciò ci dice che occorre sempre che il primo indice sia minore del secondo per poter controllare le partite, quindi se necessario vanno scambiati. Otteniamo così:


Sequenza di chiamata in campo	Elenco delle partite aggiornato

Procedendo con questo metodo si arriva ad estrarre/marcare tutte le partite. A quel punto in sequenza c'è l'ordine di chiamata delle squadre che se prese a coppie rappresentano l'ordine delle partite da giocare.

Come si traduce tutto questo in codice PHP? Diciamo subito che l'unico dato di cui c'è bisogno, è il numero delle squadre che chiamo n. La nostra funzione ritornerà l'array sequenza contenente in ogni elemento il numero di squadra da 1 a n. Il client potrà quindi utilizzare l'indice numerico per accedere ad un proprio array al fine di tradurre il valore intero in un'etichetta, nome della squadra. Nel codice si fa uso di una funzione di swap() così definita:


function swap(&$a,&$b){

    $t=$a; $a=$b; $b=$t;

}

Banalmente per $partite avremo:

$partite=array();

for($i=1; $i<$n; $i++)

    for($j=$i+1; $j<=$n;$j++ )

        $partite["$i-$j"]=true;

Ho preferito memorizzare il valore nella chiave in modo da poter utilizzare la funzione unset() quando marco in rosso una partita giocata nella procedura manuale e isset() per verificare se una certa partita è ancora da giocare.

Fatto questo occorre inizializzare la sequenza ed eliminare le partite giocate in seguito all'inizializzazione della sequenza. Oltre la sequenza occorre però un discriminante, che a parità di indice con la sequenza, informi se quell'indice di sequenza è utilizzabile o meno (il marcatore rosso nelle immagini di sequenza). Tale valore è un booleano:

$sequenza=array();
$utile=array();
for($i=1;$i<=$n;$i++){
$sequenza[]=$i;
$utile[]=true;
}

Esiste un caso particolare, ossia quando il numero di squadre è dispari. In tal caso $sequenza avrà un numero dispari di elementi in seguito all'inizializzazione, ossia l'ultima partita manca di un concorrente. Per normalizzare l'array e ricondurci al caso manuale, possiamo semplicemente richiamare la prima squadra e marcarla come non più utile, in cima all'array della sequenza.

if ($n % 2 != 0) {
$sequenza[] = 1;
$utile[] = true;
$utile[0] = false;
$n++;
}

Da questo momento assumeremo essere $n non più il numero di squadre, ma la lunghezza corrente della sequenza. Se le squadre sono pari, $n ci dice la lunghezza della sequenza dopo la prima inizializzazione. Se sono dispari, avendo aggiunto un elemento alla sequenza è stato anche incrementato di uno il valore di $n.

Occorre quindi rimuovere da $partite le partite già inserite nella sequenza in fase di inizializzazione.

for ($i = 0; $i < $n; $i++) {
$s1 = $sequenza[$i];
$s2 = $sequenza[++$i];
if ($s1 > $s2)
swap($s1, $s2);
unset($partite["$s1-$s2"]); //marcatore rosso in partite nelle immagini
}

E' questo il punto di inizio indicato nella seconda immagine di questo post. Ha quindi inizio il calcolo vero e proprio. Per prima cosa inizializzo alcune variabili utili all'interno del ciclo di ordinamento, poiché di questo si tratta tale algoritmo:


$unaCancellata = true;
$scambiati = false;
$j = $i = 0;

La variabile $unaCancellata è un flag che segnala se nel corso del ciclo una partita è stata rimossa da $partite. $scambiati è un flag che segnala se è stato necessario scambiare i due indici di squadra chiamando la funzione swap. $i è l'indice di ricerca all'interno di sequenza per la prima squadra. $j è l'indice di ricerca all'interno di sequenza per la seconda squadra.
Avremo quindi il nostro ciclo principale la cui condizione di fine è data dallo svuotamento dell'array partite:


while(!empty($partite)){
//corpo ciclo principale
}

Al suo interno c'è un primo controllo su $unaCancellata. Se una partita è stata cancellata, tutto si è svolto regolarmente e si resettare il flag. Se invece non è stata cancellata nessuna partita, vuol dire che la prima squadra trovata non deve più competere con nessun altra squadra. Quindi si porta avanti l'indice di ricerca per la prima squadra:

if($unaCancellata)

    $unaCancellata=false;

else

    $i++;

Ciò fatto si lancia la ricerca per la prima squadra utile ad essere richiamata in campo:

$n = count($sequenza);


while ($i < $n and !$utile[$i]) $i++;

$s1 = $sequenza[$i];

Ora in $s1 c'è il numero della prima squadra. Procediamo nel cercare una seconda, verificando se utile e che la partita fra le due squadre non sia stata giocata. Se non lo è si aggiorna sequenza e partite, quindi è possibile procedere al prossimo incontro. In alternativa la ricerca prosegue lungo la sequenza.


$j = $i + 1;

while ($j < $n and !$unaCancellata) {
$s2 = $sequenza[$j];
if ($s1 > $s2) {
swap($s1, $s2);
$scambiati = true;
}
if ($utile[$j] and isset($partite["$s1-$s2"])) {
unset($partite["$s1-$s2"]);
$sequenza[] = $sequenza[$i];
$sequenza[] = $sequenza[$j];
$utile[] = $utile[] = true;
$utile[$i] = $utile[$j] = false;
$unaCancellata = true;
}
if ($scambiati) {
$s1 = $s2;
$scambiati = false;
}
$j++;

Al termine del ciclo, in $sequenza c'è il risultato.

Assemblando il tutto, racchiudendolo in una funzione e dando qualche piccolo ritocco otteniamo (procedie leggendo la parte 2):

function CalcoloPartite($n) {
$partite = array();
$sequenza = array();
$utile=array();
for ($i = 1; $i <= $n; $i++){
$sequenza[] = $i;
$utile[]=true;
for ($j = $i + 1; $j <= $n; $j++)
$partite["$i-$j"] = true;
}

if ($n % 2 != 0) {
$sequenza[] = 1;
$utile[] = true;
$utile[0] = false;
$n++;
}

for ($i = 0; $i < $n; $i++) {
$s1 = $sequenza[$i];
$s2 = $sequenza[++$i];
if ($s1 > $s2)
swap($s1, $s2);
unset($partite["$s1-$s2"]);
}

$unaCancellata = true;
$scambiati = false;
$j = $i = 0;
while (!empty($partite)) {
if ($unaCancellata)
$unaCancellata=false;
else
$i++;

$n=count($sequenza);

while ($i < $n and !$utile[$i]) $i++;
$s1 = $sequenza[$i];

$j = $i + 1;
while ($j < $n and !$unaCancellata) {
$s2 = $sequenza[$j];
if ($s1 > $s2) {
swap($s1, $s2);
$scambiati = true;
}

if ($utile[$j] and isset($partite["$s1-$s2"])) {
unset($partite["$s1-$s2"]);
$sequenza[] = $sequenza[$i];
$sequenza[] = $sequenza[$j];
$utile[] = $utile[] = true;
$utile[$i] = $utile[$j] = false;
$unaCancellata = true;
}