Visualizza il feed RSS

Titolo provvisorio...

Il tifoso, l'arbitro e il calciatore...

Valuta questo inserimento
di pubblicato il 07-12-2019 alle 02:10 (506 Visite)
Prendo a prestito il titolo di una nota commedia all'italiana, perché in questo breve articolo si parla di come creare, in generale, calendari d'incontri e tornei. Strumenti utili in vari frangenti, dallo studio del comportamento sociale di volatili e mammiferi alla teoria elettorale, come pure nello sport, dalle boccette agli scacchi passando appunto per palle e palloni di varia foggia. Sappiamo però per lunga esperienza che, ogni volta che si sfiora l'argomento, il lettore medio pensa subito invariabilmente al pallone e al campionato all'italiana. Da qui, ovviamente, il titolo!

Sebbene esista perfino una fondamentale monografia completamente dedicata a tornei e affini, oltre ad interi capitoli specifici in testi di combinatorica e combinatorial designs, il metodo deterministico più elementare per la generazione di tali tornei è decisamente arcinoto - anche se porta il nome dell'oscuro scacchista austriaco Johann Nepomuk Berger. Tale attribuzione è peraltro filologicamente errata: fonti autorevolissime della storia degli scacchi (in primis la Bibbia della storia scacchistica, "The Oxford Companion to Chess", Oxford University Press, ISBN 0198661649) attribuiscono invece l'idea originale al non meno sconosciuto Richard Schurig, il quale in definitiva ha semplicemente pubblicato una serie di tavole precalcolate per vari numeri di giocatori nel 1886 sul Deutsche Schachzeitung. Berger le ha poi solo riproposte qualche anno più tardi, nel 1892-93, nel suo Schachjahrbucher.

In ogni caso, il cosiddetto "algoritmo di Berger" si trova così erroneamente referenziato un po' ovunque in letteratura, sebbene codesto signore non l'abbia in effetti inventato, e soprattutto non in forma di algoritmo ma di tavole precompilate. Le idee sottese sono antichissime, in particolare il concetto di cerniera. Il tipo di tornei che qui ci interessano è detto "round robin", esattamente come l'algoritmo di scheduling più elementare noto dalla teoria dei sistemi operativi multitasking, ben conosciuto da chiunque abbia affrontato un minimo di studi istituzionali in informatica. Se nell'uno o nell'altro caso qualche lettore fosse stato punto da vaghezza di sapere chi diavolo fosse mai questo signor Robin, si consoli: l'espressione non ha alcuna attinenza con un nome proprio e deriva semplicemente, a dispetto di molte fonti male informate, dalla corruzione anglofona del francese ruban che significa "nastro". Dunque si parla di un nastro circolare, il che è la perfetta descrizione concettuale di quel che accade: un ordine lineare, finito e limitato (la lista ordinata dei partecipanti) si trasforma - con una operazione tra le più tipiche e paradigmatiche del pensiero discreto - in un ordine circolare, periodico, ovvero finito ma non limitato, semplicemente unendo gli estremi.

La storia di questa idea, di per sé, sarebbe talmente densa ed interessante da riempire un intero tomo. Qui ci limitiamo all'ovvio e all'arcinoto, citando per l'ennesima volta l'apoftegma del piccolo Gauss alle prese con la somma dei primi cento numeri naturali. Una buona vulgata vuole che egli li scrivesse nella seguente guisa, traendo poi le opportune conclusioni dalle somme di ciascuna coppia verticale:

codice:
  1   2   3 ...  49  50
100  99  98 ...  52  51
Tale versione risulta forse meno accurata storicamente, ma massimamente "informatichese" in quanto realizza una pratica economia di risorse: in questa versione, infatti, ciascun numero viene scritto una e una sola volta. Quel che conta qui è comunque il concetto: nella lista così "ripiegata" ciascun numero "incontra" il suo omologo, come i denti delle due metà di una cerniera lampo si incastrano perfettamente gli uni negli altri quando accostati! Ciò spiega la denominazione, sovente adottata in letteratura, di algoritmo a "cerniera" per tutti i tipi di approccio derivati da questa idea. Interessante notare che la somma di ciascuna coppia di numeri in verticale è costante, ma le differenze indicano che tali coppie formano un completo sistema di differenze, che è il reale motivo algebrico per cui tale costruzione funziona.

L'algoritmo in pratica è tutto qui: si fissa arbitrariamente un pivot, e per ogni giornata si fanno scorrere in un verso stabilito tutti gli altri giocatori, in genere di una posizione (in realtà, si dimostra banalmente che qualsiasi valore di scorrimento relativamente primo al numero di partecipanti diminuito di una unità genera un calendario valido).
In questo modo, per costruzione, ciascun giocatore incontra il pivot una e una sola volta per ogni serie completa di scorrimenti (che riporta la lista esattamente nella posizione iniziale), e meccanicamente ne consegue che ogni squadra incontra una e una sola volta tutte le altre, per l'ovvia corrispondenza posizionale stabilita dalla "cerniera".
Per aggiungere un po' di spezie, è poi possibile inserire qualche banale euristica preliminare, come rimescolare la lista dei partecipanti o scegliere in modo pseudocasuale verso e ampiezza delle rotazioni (da una lista di possibili coprimi), al solo fine di ottenere calendari leggermente variati ad ogni esecuzione, mitigando la rigidità strutturale dell'algoritmo uncooked. Ribadisco tuttavia il concetto portante: è proprio in tal modo che fisicamente si svolgono molti tipi di torneo. Ad esempio, in quelli di dama e scacchi, i giocatori (tranne uno) al termine di una partita scalano fisicamente di posto attorno ad un lungo tavolo, o attorno ad una serie di singoli tavolini allineati, il che è quanto avviene peraltro anche nel ping pong ed in molti altri sport analoghi.

Il sorgente che segue, ampissimamente commentato, dimostra tutti i concetti fondamentali del banale algoritmo in questione, la cui assoluta superiorità prestazionale e concettuale rispetto ad altre bislacche soluzioni (purtroppo molto diffuse) è immediatamente palese.

codice:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "coprimes.h"

/* Limite totalmente arbitrario */
#define MAX_TEAMS 32U

typedef unsigned int uint;
typedef enum {FALSE, TRUE} Boole_t;

uint Squadre[MAX_TEAMS];
uint Calendario[MAX_TEAMS][MAX_TEAMS];

/*************************************************************************/
/*************************************************************************/
void shuffle(uint Array[], const size_t Size)
{
    size_t i;

    for (i = Size; i > 1; --i)
    {
        register uint t;
        size_t p = rand() % i;

        /* SWAP(Array[i-1], Array[rand(i)]) */
        t = Array[p];
        Array[p] = Array[i -1];
        Array[i -1] = t;
    }
}
/*************************************************************************/
/*************************************************************************/

/*************************************************************************/
/*************************************************************************/

int main()
{
    size_t NumSquadre = 10;
    size_t pivot, Giornate;
    size_t Shift;
    size_t i, first, temp;

    randomize();

    /*
    ** Primo passo: si genera una permutazione pseudocasuale delle
    ** squadre, per introdurre un po' di nondeterminismo rispetto
    ** all'ordine naturale.
    */
    for (i = 0; i < NumSquadre; ++i)
    {
        Squadre[i] = i;
    }
    shuffle(Squadre, NumSquadre);

    /*
    ** Secondo passo: si sceglie in modo pseudocasuale anche la
    ** squadra pivot, ossia il punto fisso richiesto dall'algoritmo
    ** di Berger.
    */
    pivot = rand() % NumSquadre;

    /*
    ** La squadra pivot viene posizionata al termine all'array.
    ** Se il numero di squadre viene immesso dall'utente, in caso di
    ** valore dispari si aggiungera' invece in tale posizione una squadra
    ** fittizia, codificata in modo univoco (es. 99), che rappresenta il
    ** "Riposo". Chi "incontra" tale squadra pivot, evidentemente, salta
    ** il turno.
    **
    ** In questo modo le squadre saranno sempre e comunque in numero pari.
    */
    temp = Squadre[pivot];
    Squadre[pivot] = Squadre[NumSquadre -1];
    Squadre[NumSquadre -1] = temp;

    /*
    ** Si noti che qui il valore viene diminuito di una unita', per
    ** semplificare i riferimenti in tutto il resto del programma.
    */
    --NumSquadre;
    Giornate = NumSquadre;
    first = 0;

    /*
    ** Terzo passo: le rotazioni richieste dall'algoritmo non sono
    ** limitate ad un passo unitario. Si veda anche il file coprimes.h.
    ** Si sceglie quindi un valore per la rotazione: sono ammessi, oltre
    ** all'unità, tutti i numeri coprimi con NumSquadre -1.
    ** Attenzione al peculiare indirizzamento dell'array dei coprimi.
    */
    Shift = coprimes[(NumSquadre -2) >> 1][rand() % coprimes[(NumSquadre -2) >> 1][NUM_COPRIMES]];
    if (rand() & 1)
    {
        /*
        ** Come ulteriore elemento di dinamizzazione, si sceglie anche il
        ** verso di rotazione in modo pseudocasuale. La sostanziale
        ** (e non banale) simmetria dei coprimi inferiori ad un valore
        ** dato garantisce che, se il naturale 1 < k < n è coprimo a n,
        ** allora lo sarà anche n - k.
        */
        Shift = NumSquadre - Shift;
    }

    printf("Squadre........... %d\nPivot............. %d\n"
           "Shift............. %d\n",
           NumSquadre +1, Squadre[NumSquadre], Shift);

    /*
    ** Implementazione dell'algoritmo "a cerniera".
    ** La squadra pivot incontra, a rotazione, tutte le altre.
    ** Questo vincolo viene esteso meccanicamente alle altre coppie.
    */
    for (i = 0; i < Giornate; ++i)
    {
        size_t id1;
        int ofs;

        printf(">> Giornata %2d *******************************************************\n"
               "%d-%d", i +1, Squadre[NumSquadre], Squadre[first]);

        Calendario[Squadre[NumSquadre]][Squadre[first]] = i+1;
        Calendario[Squadre[first]][Squadre[NumSquadre]] = i+1;

        for (id1 = (first +1) % NumSquadre, ofs = NumSquadre -2; ofs > 0; ofs -= 2)
        {
            size_t id2 = (id1 + ofs) % NumSquadre;

            printf(", %d-%d", Squadre[id1], Squadre[id2]);

            Calendario[Squadre[id1]][Squadre[id2]] = i+1;
            Calendario[Squadre[id2]][Squadre[id1]] = i+1;
            id1 = (++id1) % NumSquadre;
        }
        puts("");
        first = (first + Shift) % NumSquadre;
    }

    puts("**********************************************************************\n");


    /*
    ** Fine lavoro. Stampa della matrice torneo.
    */
    for (i = 0; i <= NumSquadre; ++i)
    {
         size_t j;
         for (j = 0; j <= NumSquadre; ++j)
         {
            printf("%2d ", Calendario[i][j]);
         }
         puts("");
    }

    return EXIT_SUCCESS;
}
/* EOF: cal_berger.c */
Lo header referenziato:
codice:
#ifndef __COPRIMES_H__
#define __COPRIMES_H__

#ifndef uchar_t
  typedef unsigned char uchar_t;
#endif

/*
** Le rotazioni valide per la creazione di un calendario di incontri
** non sono limitate a quella unitaria, ma includono tutti e soli i valori
** coprimi a n-1, dove n è il numero delle squadre. I vincoli della
** implementazione garantiscono per costruzione che n-1 sia sempre dispari,
** dunque occorre e basta limitarsi a siffatti valori nella costruzione della
** tabella dei coprimi.
**
** L'ultima locazione in tabella riporta il numero di coprimi, aumentato
** di una unità per tener conto della presenza del primo divisore improprio,
** l'unità, aggiunto per omogeneità di trattamento: in buona sostanza, 
** abbiamo qui tabulato la funzione totiente di Euler phi(n) per piccoli valori 
** di n, tutti dispari.
**
** La rappresentazione scelta obbedisce evidentemente a criteri di massima
** efficienza nella selezione pseudorandom a runtime, piuttosto che a istanze
** di minimizzazione del footprint in memoria - che avrebbero invece spinto
** all'uso di bitmap o, al limite, di un array booleano.
**
*/
#define MAX_VAL 31
#define NUM_COPRIMES (MAX_VAL -1)

uchar_t coprimes[][MAX_VAL] = {
/*  3 */ {1,  2,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  2},
/*  5 */ {1,  2,  3,  4,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  4},
/*  7 */ {1,  2,  3,  4,  5,  6,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  6},
/*  9 */ {1,  2,  4,  5,  7,  8,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  6},
/* 11 */ {1,  2,  3,  4,  5,  6,  7,  8,  9, 10,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 10},
/* 13 */ {1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 12},
/* 15 */ {1,  2,  4,  7,  8, 11, 13, 14,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  8},
/* 17 */ {1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15, 16,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 16},
/* 19 */ {1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15, 16, 17, 18,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 18},
/* 21 */ {1,  2,  4,  5,  8, 10, 11, 13, 16, 17, 19, 20,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 12},
/* 23 */ {1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22,  0,  0,  0,  0,  0,  0,  0,  0, 22},
/* 25 */ {1,  2,  3,  4,  6,  7,  8,  9, 11, 12, 13, 14, 16, 17, 18, 19, 21, 22, 23, 24,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 20},
/* 27 */ {1,  2,  4,  5,  7,  8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 25, 26,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 18},
/* 29 */ {1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28,  0,  0, 28},
/* 31 */ {1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 30} };

#endif
/* EOF: coprimes.h */
Per la funzione totiente di Euler φ(n) si veda anche: OEIS A000010

Tutto qui: semplice, elegante, efficace e soprattutto efficiente.

Nota conclusiva: il calendario così generato è ovviamente dimostrativo e generico, ergo non tiene conto delle peculiarità di questo o quello sport (ad esempio l'alternanza tra partite "in casa" e non, che comunque è poco più che una questione di stampa), perché qui non svolgiamo i compiti per casa di nessuno, ma è perfetto per illustrare i concetti dell'algoritmo e le sue più immediate varianti, per fare in modo che vi siano sempre piccole differenze nei calendari generati di volta in volta.
Ecco un banale test run.

codice:
y:\>cal_berger
Squadre........... 10
Pivot............. 4
Shift............. 5
>> Giornata  1 *******************************************************
4-0, 6-7, 3-2, 5-9, 1-8
>> Giornata  2 *******************************************************
4-8, 9-1, 2-5, 7-3, 0-6
>> Giornata  3 *******************************************************
4-6, 3-0, 5-7, 1-2, 8-9
>> Giornata  4 *******************************************************
4-9, 2-8, 7-1, 0-5, 6-3
>> Giornata  5 *******************************************************
4-3, 5-6, 1-0, 8-7, 9-2
>> Giornata  6 *******************************************************
4-2, 7-9, 0-8, 6-1, 3-5
>> Giornata  7 *******************************************************
4-5, 1-3, 8-6, 9-0, 2-7
>> Giornata  8 *******************************************************
4-7, 0-2, 6-9, 3-8, 5-1
>> Giornata  9 *******************************************************
4-1, 8-5, 9-3, 2-6, 7-0
**********************************************************************

 0  5  8  3  1  4  2  9  6  7
 5  0  3  7  9  8  6  4  1  2
 8  3  0  1  6  2  9  7  4  5
 3  7  1  0  5  6  4  2  8  9
 1  9  6  5  0  7  3  8  2  4
 4  8  2  6  7  0  5  3  9  1
 2  6  9  4  3  5  0  1  7  8
 9  4  7  2  8  3  1  0  5  6
 6  1  4  8  2  9  7  5  0  3
 7  2  5  9  4  1  8  6  3  0

y:\>cal_berger
Squadre........... 10
Pivot............. 3
Shift............. 2
>> Giornata  1 *******************************************************
3-7, 0-2, 6-9, 1-4, 8-5
>> Giornata  2 *******************************************************
3-6, 1-0, 8-7, 5-2, 4-9
>> Giornata  3 *******************************************************
3-8, 5-1, 4-6, 9-0, 2-7
>> Giornata  4 *******************************************************
3-4, 9-5, 2-8, 7-1, 0-6
>> Giornata  5 *******************************************************
3-2, 7-9, 0-4, 6-5, 1-8
>> Giornata  6 *******************************************************
3-0, 6-7, 1-2, 8-9, 5-4
>> Giornata  7 *******************************************************
3-1, 8-6, 5-0, 4-7, 9-2
>> Giornata  8 *******************************************************
3-5, 4-8, 9-1, 2-6, 7-0
>> Giornata  9 *******************************************************
3-9, 2-4, 7-5, 0-8, 6-1
**********************************************************************

 0  2  1  6  5  7  4  8  9  3
 2  0  6  7  1  3  9  4  5  8
 1  6  0  5  9  2  8  3  4  7
 6  7  5  0  4  8  2  1  3  9
 5  1  9  4  0  6  3  7  8  2
 7  3  2  8  6  0  5  9  1  4
 4  9  8  2  3  5  0  6  7  1
 8  4  3  1  7  9  6  0  2  5
 9  5  4  3  8  1  7  2  0  6
 3  8  7  9  2  4  1  5  6  0

y:\>cal_berger
Squadre........... 10
Pivot............. 2
Shift............. 1
>> Giornata  1 *******************************************************
2-3, 1-0, 6-8, 7-5, 4-9
>> Giornata  2 *******************************************************
2-1, 6-3, 7-0, 4-8, 9-5
>> Giornata  3 *******************************************************
2-6, 7-1, 4-3, 9-0, 5-8
>> Giornata  4 *******************************************************
2-7, 4-6, 9-1, 5-3, 8-0
>> Giornata  5 *******************************************************
2-4, 9-7, 5-6, 8-1, 0-3
>> Giornata  6 *******************************************************
2-9, 5-4, 8-7, 0-6, 3-1
>> Giornata  7 *******************************************************
2-5, 8-9, 0-4, 3-7, 1-6
>> Giornata  8 *******************************************************
2-8, 0-5, 3-9, 1-4, 6-7
>> Giornata  9 *******************************************************
2-0, 3-8, 1-5, 6-9, 7-4
**********************************************************************

 0  1  9  5  7  8  6  2  4  3
 1  0  2  6  8  9  7  3  5  4
 9  2  0  1  5  7  3  4  8  6
 5  6  1  0  3  4  2  7  9  8
 7  8  5  3  0  6  4  9  2  1
 8  9  7  4  6  0  5  1  3  2
 6  7  3  2  4  5  0  8  1  9
 2  3  4  7  9  1  8  0  6  5
 4  5  8  9  2  3  1  6  0  7
 3  4  6  8  1  2  9  5  7  0

y:\>
Si osservi la peculiare simmetria della matrice degli incontri rispetto alla diagonale principale: quel che si ottiene, infatti, è esattamente un quadrato latino simmetrico, ossia una matrice nxn nella quale ciascun elemento 0...n-1 compare esattamente una volta per ciascuna riga e colonna, con la peculiarità aggiuntiva che ogni riga i-esima è identica alla colonna i-esima.

aggiornamento da 11-01-2020 a 22:00 di M.A.W. 1968

Categorie
Programmazione , Scienza