Calcolo delle competizioni senza ripetizioni con massimo riposo - La Patch (Parte2/2)

E' vero che l'algoritmo consente il massimo riposo, ma tale riposo è garantito solo per la prima squadra estratta dalla sequenza. La seconda è scelta partendo dalla più, fino alla meno riposata, purché non abbia ancora giocato una partita con la prima estratta. Man mano che le partite si esauriscono esiste la possibilità che una squadra si trovi a dover competere in partite adiacenti. Nella maggior parte dei casi tale anomalia non si verifica, e quando si verifica  presenta una o due ricorrenze nella sequenza delle partite.

Esempio di anomalia a 6 squadre

L'anomalia nasce dalla circostanza per cui la squadra più riposata è la 1, ma le partite in cui è coinvolta la squadra 1 sono terminate a meno della 1-6. Quindi il sistema segna come partita 13 la 1-6. La squadra 6 si trova a giocare due volte consecutivamente senza poter riposare.

Tale anomalia, per numero di squadre da 5 a 50 si verifica per 6, 8, 10, 25, 35, 36, 42, 45 e 48 e da 5 a 105 nel 33% dei casi.

Da una analisi dei punti anomali per diverse quantità di squadre, mi sono accorto che è possibile dare una partita di riposo. In particolare se il numero partite è dispari, è possibile ritardare la partita scambiandola con quella successiva l'anomalia. Nel caso della figura precedente si scambia la partita 13 con la 14.

Esempio a 6 squadre con patch

Se invece il numero di partite è pari o l'anomalia si presente come ultima partita, allora si può scambiare la partita precedente l'anomalia con quella ancora prima. Applicando iterativamente tale metodo (di norma una o due volte) si risolvono le anomalie e si ottiene il turno di riposo per la squadra penalizzata.

La funzione di patch risulta quindi essere (la funzione di swap è quella vista al post precedente):

function patch(&$giocate) {   
    do{     
        $sanate = false;
        if (($n = count($giocate)) >= 15) {
            for ($i = 1; $i < $n; $i++) {
                if (array_search($giocate[$i][0], $giocate[$i - 1]) !== false or
                    array_search($giocate[$i][1], $giocate[$i - 1]) !== false) {
                    $sanate=true;
                    if ($n % 2 == 0 or $i == $n - 1)
                        swap($giocate[$i - 1], $giocate[$i - 2]);
                    else
                        swap($giocate[$i], $giocate[$i + 1]);
                }
            }
        }
    }while($sanate); 
}


Per ottenere le giocate senza appesantire ulteriormente il codice con un'altro ciclo, occorre modificare la funzione di calcolo principale in modo che non ritorni  più la sequenza ma le giocate come coppie di squadre  e richiamare al suo interno la funzione di patch.

function CalcoloPartite($n) {   
    $partite = array();
    $sequenza = array();
    $utile = array();  
    $giocate = array(); //Modifica la codice precedente
    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"]);
        $giocate[]=array($s1,$s2); //Modifica al codice precedente
    }

    $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"]);
                    $giocate[]=array($s1,$s2); //Modifica al codice precedente
                    $sequenza[] = $sequenza[$i];
                    $sequenza[] = $sequenza[$j];
                    $utile[] = $utile[] = true;
                    $utile[$i] = $utile[$j] = false;
                    $unaCancellata = true;    
            }
            if ($scambiati) {
                $s1 = $s2;
                $scambiati = false;
            }
            $j++;
        }
    }           


    patch($giocate); //Patch al risultato
 
    return $giocate;
}


La patch è testata per valori di $n da 2 a 240. Oltre non ho eseguito dei test, ma è probabile che funzioni anche per i valori superiori.