Algoritme wedstrijdschema
Hallo,
Ik ben op zoek naar een algoritme (ik hoop dat het voldoende wiskundig is). Het algoritme moet in staat zijn een halve wedstrijdschema te maken waarbij alle teams 1 wedstrijd tegen elkaar spelen. Ook mag elk team maar 1 wedstrijd per ronde spelen. Het aantal teams in een pool is even. De volgende dingen heb ik zelf reeds uitgevonden:
- aantal rondes is: teams-1
- aantal wed per ronden is: teams/2
- aantal wedstrijden is: (teams-1)·(teams/2)
Ik hoop zo voldoende info gegeven te hebben.
Gr. Xander
Xander
Student hbo - vrijdag 26 maart 2004
Antwoord
N.B. Peter Pesch reageerde met de opmerking dat het allemaal nog wat eenvoudiger kan, zie Re: Algoritme wedstrijdschema.
Hoi Xander,
ik denk dat dit ergens al wel opgelost zal zijn, maar op www.wisfaq.nl heb ik het nog niet gevonden, dus geef ik hier een mogelijke oplossing via een inductief algoritme,
daartoe moet ik en passant ook iets zeggen over het geval dat er een oneven aantal teams. Let wel: er zijn meerdere oplossing bij jouw eisen, ik heb een zo eenvoudig mogelijke oplossing gekozen. Je kunt natuurlijk altijd andere schemas krijgen door de teams of de ronden te verwisselen. Inmiddels ben ik zelf mijn hoofd aan het pijnigen over de vraag of je op die manier alle andere mogelijke schemas kunt krijgen, maar daar ben ik nog niet uit.
Hieronder geef ik eerst een aantal oplossingen voor kleine aantallen teams en ga aan de hand daarvan een algemene methode schetsen.
2) Voor een competitie met twee spelers is het volgende competitieschema de enige mogelijkheid:
Hierbij moet je de bovenste regel eigenlijk weglaten, dat is slechts de kop waarin de spelende teams gemeld worden, de regels daaronder zijn per ronde de tegenstanders. Dit is niet de zuinigste manier om het schema op te schrijven (de informatie over elke wedstrijd staat er dubbel in), maar om uit te leggen wat ik doe vind ik het wel handig om het nu zo te doen.
3) Met drie teams zal er elk ronde één team niet kunnen spelen. Zonder de algemeenheid te schaden kun je er van uitgaan dat team 1 de eerste twee ronden speelt tegen teams 2 resp. 3:
En tenslotte moeten de teams 2 en 3 natuurlijk nog tegen elkaar spelen, dat laten we in de laatste ronde gebeuren. Daarmee spelen we dus wel een ronde meer dan nodig zou zijn als alles goed uit zou komen.
4) Met vier teams is er eigenlijk ook maar één mogelijkheid. Je kunt de teams namelijk zo nummeren dat je een team, nummer 1 noemt en de teams waartegen zij in ronde 1,2,3 spelen, noem je 2,3,4. Omdat je natuurlijk weet dat, als team a tegen team b speelt, ook team b tegen team a moet spelen, ligt dan al een groot deel van het schema vast; als je ook bedenkt dat zowel in elke rij als in elke kolom elk team precies één keer voor moet komen, dan blijkt alles vast te liggen. Dus:
5) Bij vijf teams wordt gewoon zoeken wat meer werk. Eerst dacht ik nog dat je vraag naar een algoritme voor even aantallen teams erop gebaseerd was dat het oneven geval te moeilijk zou zijn. Dan moet er immers elke ronde een team overblijven, terwijl het voor even aantallen precies goed uit komt. Ik begrijp nu dat het waarschijnlijk andersom is en dat jij het algoritme voor oneven aantallen al kent, namelijk als je de teams nummert van 1 t/m n, dan moet je in ronde r team i koppelen met (r+2-i)n, waarbij (·)n de rest bij deling door n voorstelt, echter met (n)n = n. Dit komt er overigens op neer dat je op elke rij de teams cyclisch doorschuift, maar dan in omgekeerde volgorde.
Om te bewijzen dat dit goed zit moet je allereerst laten zien dat dan ook team (r+2-i)n tegen i speelt:
(r+2-(r+2-i)n)n = (r+2-(r+2-i))n = i.
Bovendien moet het zo zijn dat elk team alle andere tegen komt. M.a.w. voor elk team i en j moet er een ronde r zijn zodanig dat (r+2-i)n = j, oftewel r = (i+j-2)n, waarbij r = n als (i+j-2)n = 0. Het is duidelijk dat dit altijd goed gaat, met r een van de ronden 1 t/m n.
Waarom is dit dan niet ook de oplossing voor even n? Het punt is dat het competitieschema voor oneven n uit n ronden bestaat, terwijl je voor even n met een ronde minder aan kunt. Hoe je dat voor elkaar kunt krijgen volgt nog.
6) Voor zes teams kunnen we op de volgende manier een competitieschema opstellen: allereerst verdelen we de 6x6 tabel in vier delen van 3x3. In de onderste helft plaatsen we alle wedstijden van de linker drie teams tegen de rechter drie teams, op een systematische wijze, nl (bedenk dat we de wedstrijden van team 1 altijd al hebben ingevuld) door 123 in elke rij onder 456 te zetten, zodanig cyclisch verschoven dat 1 op de diagonaal blijft (zie hieronder), linker schema. Van de bovenste helft is de bovenste rij al ingevuld, en we gaan verder door de competitie van drie teams (zie onder kopje 3) hier in te vullen. Nu hebben we echter nog open gaten en bovendien moeten 2 en 3, en 5 en 6 nog tegen elkaar spelen. En laat dat nu net allebei in één klap op te lossen zijn door de wedstrijden van 2 en 3 tegen 5 en 6 uit de bovenste regel van de onderste helft naar boven te verplaatsen en op de vrijkomende plaatsen de wedstijden van 2 tegen 3 en 5 tegen 6 te plaatsen. Oftewel:
| 1 | 2 | 3 | 4 | 5 | 6 | | 2 | 1 | | 5 | 4 | | | 3 | | 1 | 6 | | 4 | | 4 | 5 | 6 | 1 | 2 | 3 | | 5 | 6 | 4 | 3 | 1 | 2 | | 6 | 4 | 5 | 2 | 3 | 1 |
|
| | 1 | 2 | 3 | 4 | 5 | 6 | | 2 | 1 | 6 | 5 | 4 | 3 | | 3 | 5 | 1 | 6 | 2 | 4 | | 4 | 3 | 2 | 1 | 6 | 5 | | 5 | 6 | 4 | 3 | 1 | 2 | | 6 | 4 | 5 | 2 | 3 | 1 |
|
7) Dit kan weer volgens het algoritme voor oneven aantallen, zie onder 5).
8) De truc van het opdelen, zoals toegepast bij 6), werkt hier nog eenvoudiger: We verdelen de 8x8 tabel in vier vierkanten van 4x4. In de bovenste twee vierkanten komt gewoon het competitieschema voor 4 teams. Omdat 4 even is, past dat nu precies. In de onderhelft doen we precies hetzelfde als bij 6), maar dit keer hoeven we niet meer extra te schuiven op de bovenste regel.
En dan nu voor algemene n:
* als n oneven is, dan kunnen we de formule voor oneven n zoals gegeven onder 5) gebruiken.
* als n = 2·k, met k even, dan is de werkwijze als bij 8): we verdelen in vier vierkanten van k x k. Merk op dat je de onderste helft ook in formulevorm kunt brengen door te zeggen dat je voor i = 1 t/m k team i in ronde r (r = k t/m n-1) laat spelen tegen team k+(i+r)k (dat is er een uit k+1 t/m n). Je hoeft nu alleen te bewijzen dat op die manier alle teams uit 1 t/m k alle teams uit k+1 t/m n tegenkomen, want dat k+(i+r)k ook tegen i speelt is per definitie (je kunt ook uitrekenen hoe je dat in formulevorm giet).
* als n = 2·k, met k oneven, dan wordt het, net als bij 6), wat lastiger. Weer deel je de tabel in vier vierkanten van k x k, maar nu kun je de bovenhelft niet goed vullen met het competitieschema voor k teams: er blijven open plekken in zitten en je hebt een ronde teveel. Maar, als je links- en rechtsboven hetzelfde schema gebruikt, dan zitten de open plekken op dezelfde plaatsen en kun je dus de wisseltruc met de bovenste regel van de onderste helft weer perfect toepassen! Het enige dat je hiervoor nog moet bewijzen is dat elk van de k teams precies één ronde niet speelt, maar dat is niet zo moeilijk (het algoritme voor oneven n geeft immers maar één ronde te veel). Het volgt ook uit het feit dat (r+2-i)k = i dan en slechts dan als (r)k = (2·(i-1))k. Hier zie je nogmaals het verschil met even k: modulo oneven k kun je "delen door 2" zodat er per ronde maar één team is dat niet speelt, terwijl er voor even k, altijd twee oplossingen per ronde te vinden zijn.
Tot slot: om mijn bewijs kracht bij te zetten, volgt hieronder een routine die dit algoritme toepast om competitieschemas te vinden. Helaas is matlab de enige programmeertaal die ik tot mijn beschikking heb (werkt wel erg makkelijk met matrices), dus het is in matlab geschreven. Dat lijkt wel erg op C, dus als je het wilt omschrijven naar een andere taal zal dat ook wel lukken.
Wat deze routine betreft:
Als je hem aanroept met competitie(n), dan geeft hij de tabel, zoals ik die hierboven ook meermalen heb gebruikt, maar dan tellend van 0 t/m n-1. Als je hem aanroept met competitie({'Mamma Mia', 'Terra Nova', 'Via Via', 'Joco Dokus', 'Hia Cintus'}), dan geeft hij een tekststring met een competitieschema voor de genoemde teams (per ronde worden de wedstrijden opgesomd). Als je op de plaats van het eerste team 'per team' opneemt, dan worden per team de wedstrijden in de verschillende ronden gegeven.
Met vriendelijke groet,
Guido Terra
gt
dinsdag 30 maart 2004
©2001-2024 WisFaq
|
Re: Algoritme wedstrijdschema