Tra parentesi, su wikipedia fanno sempre le cose a metà, o anche meno.
Il cosiddetto "algoritmo di Berger" in realtà era solo una serie di tabelle precompilate, per vari numeri di giocatori. Peraltro, anche se ne porta il nome, il metodo non è neppure stato inventato da tale Johann Nepomuk Berger, "noto" scacchista austriaco ottcentesco, ma da Richard Schurig, altro illustrissimo sconosciuto che comunque ha pubblicato tali tabelle nel 1886 sul Deutsche Schachzeitung. Berger le ha semplicemente riproposte qualche anno più tardi, nel 1892/93, nel suo Schachjahrbucher. Così riporta la vera e propria Bibbia della storia scacchistica: "The Oxford Companion to Chess", Oxford University Press, ISBN 0-19-866164-9.
In ogni caso, si tratta di un metodo concepito in un'epoca anni luce lontana dall'invenzione di linguaggi come Java e C++, quindi è semplicemente una bestemmia affermare che sia "fatto apposta" per questo o per quello...
Si tratta di un algoritmo semplicissimo e universale, basato su un criterio cardine della matematica discreta, che possiamo facilmente fare risalire a Gauss: il folding di un elenco, ovvero l'accostamento dei due estremi di un intervallo, in modo realizzare una "coda circolare" da un ordine lineare.
L'ovvia interpretazione della lista così "ripiegata" è che 1 "incontra" 100, 2 "incontra" 99, eccetera.codice:1 2 3 ... 50 100 99 98 ... 51
Tra l'altro le descrizioni algoritmiche normalmente in circolazione fanno riferimento, per ben che vada, ad un singolo criterio fisso adottato nella compilazione delle tabelle: in realtà esistono delle facilissime generalizzazioni matematiche che possono rendere meno predicibile, e quindi più stocastico, il risultante schema di torneo. Tenendo infatti fissa una qualsiasi delle posizioni, si fanno ad ogni iterazione ruotare tutte le altre, a destra o a sinistra, di un numero di posizioni qualsiasi, purché sia relativamente primo al numero totale di elementi. Quindi lo shift a destra/sinistra di una singola posizione, usato in origine dagli scacchisti ottocenteschi, non è che un caso particolare dell'algoritmo generalizzato.
Last, but not least, nessun obbligo è dato sull'ordine iniziale, e quindi è possibile partire da una permutazione pseudocasuale (vedi shuffle Knuth-Fisher-Yates, o meglio ancora il recente Myrvold-Ruskey) della lista dei partecipanti, applicando poi l'algoritmo per la generazione del calendario.
Sfortunatamente non ho tempo di dilungarmi ulteriormente, ma qui vi sono già sufficienti elementi per costruire la migliore implementazione possibile di un simile algoritmo, in un qualsivoglia linguaggio.
Rispondi quotando
