Koodit: Täyskierrosturnauksen paritus

Tässä koodivinkissä esitellään täyskierrosturnauksen paritusalgoritmi. Täyskierrosturnaus tarkoittaa turnausta, jossa jokainen kilpailija pelaa kerran jokaista vastustajaa vastaan. Paritus on taas luettelo, joka kertoo kuka on kenenkin vastustaja eri kierroksilla.

Oikein paritetussa täyskierrosturnauksessa on aina n-1 kierrosta, kun siihen osallistuu n pelaajaa. Algoritmin triviaali tapaus on n=1, jolloin mitään turnausta ei voida pelata. Kaikilla kokonaisluvuilla n>1 se taas toimi saman periaatteen mukaisesti.

Algoritmia voi soveltaa esim. jalkapallopelin liigaotteluiden järjestämisessä tai shakkikerhon pikapeli-illassa. Se on yleisesti tunnettu skedulointialgoritmi, jonka mahdollista nimeä kirjoittaja ei kuitenkaan tunne.

Monissa peleissä on puolten valinnalla suuri merkitys. Shakissa on edullisempaa pelata valkeilla, ja jalkapallossa puhutaan usein kotikenttäedusta. Siksi hyvässä parituksessa jokainen osallistuja saa edullisemman aseman noin puolessa pelaamistaan peleissä. Tässä vinkissä käytetään sanaa aloittaja kuvaamaan puolta, jolla on edullisempi asema.

Algoritmin kuvaus

Algoritmia sovelletaan taulukkoon, jossa on parillinen määrä kilpailijoita. Mikäli turnauksessa on pariton määrä osallistujia, määrä saadaan parilliseksi ottamalla mukaan ns. tyhjä pelaaja. Se, jonka vuoro on pelata tyhjää pelaajaa vastaan, on vapaakierroksella, ts. ei pelaa ollenkaan. Algoritmin toiminta ei riipu siitä, onko yksi pelaajista tyhjä vai ei. Kierrosten määrä on aina n-1.

Taulukon indeksit alkavat tässä vinkissä yhdestä. Hyvä paikka tyhjälle pelaajalle on indeksissä 1. Jokaiselle osallistujalle voi arpoa oman numeron käytetyltä väliltä, jotta osallistujien nimiä ei tarvitse käyttää algoritmin toteutuksessa. Yhtä hyvin taulukon alkion tyyppi voi olla jokin sopiva pelaajatietue tai osoitin sellaiseen.

Tämän vinkin esimerkeissä pelaajia kuitenkin merkitään kirjaimilla A-F, jotta numerot eivät menisi sekaisin taulukon indeksien kanssa.

Alussa pelaajat laitetaan taulukkoon mielivaltaisessa järjestyksessä. Se voidaan vaikkapa arpoa, muttä tämän vinkin esimerkeissä käytetään aakkosjärjestystä. Tästä taulukosta muodostetaan otteluparit joka kierroksella saman säännön mukaan. Ensimmäinen paritus tapahtuu ennen kuin taulukon alkioita liikutetaan millään tavalla.

Sääntö määrää, että parit otetaan taulukon indekseistä i ja n+1-i, missä i käy välillä 1 - n/2. Siten esimerkiksi kuuden pelaajan turnauksessa parien indeksit taulukossa ovat seuraavat. Aloittajan määrääminen selitetään seuraavana.

1 ja 6+1-1, eli 1 ja 6 (aloittaja vaihtelee)
2 ja 6+1-2, eli 2 ja 5 (aloittaja aina indeksistä kaksi)
3 ja 6+1-3, eli 3 ja 4 (aloittaja aina indeksistä neljä)

Pareista pelin aloittajaksi valitaan aina se, jolla on taulukossa parillinen indeksi. Tämä takaa, että aloittajaetu vaihtelee mahdollisimman tasaisesti pelaajien vaihtaessa paikkaa taulukossa. Poikkeuksena on kuitenkin liikkumaton pelaaja 1, joka saa aloittajaedun aina parillisilla kierroksilla, ja jonka vastustaja saa aloittajaedun parittomilla.

Miten pelaajat sitten liikkuvat kierrosten jälkeen? Kun yksi kierros on pelattu, tehdään taulukolle osittaiskierto ennen seuraavaa paritusta. Osittaiskierto tarkoittaa kaikkien alkioiden paitsi ensimmäisen siirtoa yhden oikealle. Lisäksi viimeinen alkio tuodaan paikalle 2. Näin ollen kierrot aiheuttavat kuuden pelaajan turnauksessa (kirjaimat A-F) seuraavanlaiset sijoitukset.

   aluksi: A B C D E F
1. kierto: A F B C D E
2. kierto: A E F B C D
3. kierto: A D E F B C
4. kierto: A C D E F B

Neljännen kierron ja sitä seuraavan viidennen kierroksen jälkeen turnaus on ohi, koska kuuden pelaajan täyskierrosturnauksessa pelataan viisi kierrosta. Jokaista kiertoa seuraava paritus tapahtuu aina samojen taulukon indeksien perusteella. Esimerkkinä parituksesta otettakoon vielä 3. kierron jälkeinen tilanne.

taulukko: A D E F B C
indeksit: 1 2 3 4 5 6

Paritus, missä aloittaja ensin:
A - C (A aloittaa, koska on neljäs (parillinen) kierros)
D - B (D aloittaa, koska D:n indeksi on kaksi)
F - E (F aloittaa, koska F:n indeksi on neljä)

Voidaan osoittaa menetelmän takaavan, ettei kukaan joudu pelaamaan kahdesti samaa vastustajaa vastaan tai olemaan enemmän kuin yhden kierroksen aikana vapaakierroksella (ja sekin vain, kun osallistujia on pariton määrä). Lisäksi menetelmä takaa aloitusedun parhaimman mahdollisen jakaantumisen osallistujien kesken. On mahdotonta jakaa se täysin tasapuolisesti.

Aloitusedun epätasaisen jakautumisen voi kumota kokonaan vain, jos pelataan kaksi peräkkäistä täyskierrosturnausta ja vaihdetaan jokaisessa ottelussa aloitusetu.

Osittaiskierto

// Osittaiskierto pseudokoodina
// funktion saaman taulukon koko on aina parillinen

funktio osittaiskierto
: parametri kilpailijat, taulukko 1 - n
    väliaikainen <- kilpailijat[ n ]
    silmukka, jossa i alkaa arvosta n ja laskee arvoon 3
        kilpailijat[ i ] <- kilpailijat[ i-1 ]
    silmukan loppu
    kilpailijat[ 2 ] <- väliaikainen
    palauta taulukko

Paritus

// Paritus pseudokoodina
// funktion saaman taulukon koko on aina parillinen

// Funktio palauttaa listan kilpailijapareja, joissa
// parin ensimmäinen jäsen on aloittaja.

funktio paritus
: parametri kilpailijat, taulukko 1 - n
: parametri kierros, kokonaisluku
    paritus <- uusi lista, arvot kilpailijapareja
    jos kierros on parillinen
        paritus.lisää (uusi pari, kilpailijat[ 1 ] ja [ n ])
    muutoin
        paritus.lisää (uusi pari, kilpailijat[ n ] ja [ 1 ])
    silmukka, jossa i alkaa arvosta 2 ja nousee arvoon n/2
        pari <- uusi pari, kilpailijat[ i ] ja [ n+1-i ]
        jos i on pariton
           pari.vaihda_alkioita
        paritus.lisää (pari)
    silmukan loppu
    palauta paritus