Omdw : Overwegingen poule algoritmen Bedum 7-4-1994
Aan : Henk Kolk
Van : Menno S Ter Haseborg
Om te komen tot een poule voor de wedstrijd tafel onderscheid ik zes stappen:
a: Poule_indeling
b: Poule_toewijzing
c: Poule_splitsing
d: Poule_mat
e: Poule_plaatsing
f: Poule_afbeelding
Het Poule_indelen heeft inzich het bekende probleem hoe deel ik de judoka's
in , in gewichten/leeftijden (zo mogelijk Klassen,Kyu graden) . Ik wil hier
nu niet verder op ingaan . De Poule_indeling geeft een verzameling Indelingen.
Iedere Indeling bestaat uit een Poul_hoofd en een of meerdere Poule_grenzen.
Poul_hoofd = ( Matnummer , weegtijd , aanvangstijd , wedstrijdduur ,
winnaars )
winnaars = ( 1 , 2 , 3 , 3 ) , ( 1 , 2 , 3 , 4 )
weegtijd = aanvangstijd - aantal_tewegen_deelnemers * n min
wedstrijdduur = ( wedstrijdtijd , aantalwedstrijden )
aantalwedstrijden = ( aantaldeelnemers , poule_systeem )
Poule_grenzen = ( geslacht , leeftijdgrenzen , gewichtsgrenzen ,
klassegrenzen , kyu's )
Indeling = Poul_hoofd { Poule_grenzen }..
Indelingen = { Indeling }..
Het Poule_toewijzen geeft iedere deelnemer een Indeling met als resultaat
een Toewijzing welke bestaat uit een verzameling Organisatie's welke op
hun beurt bestaat uit een verzameling deelnemers behorend bij de Indeling.
Toewijzing = ( Indeling , { Organisatiedeelnemers }.. )
Organisatiedeelnemers = { deelnemers }..
De doorsnede Organisatiedeelnemers (over alle Toewijzingen) moet leeg zijn !
De range orde van de Organisatiedeelnemers in de Toewijzing is niet relevant.
De Poule_splitsing verzorgt de binnen de gewenste wedstrijdmethode
de grote van de poules . Dit is geheel afhankelijk van de doelstelling
van de tournooiorganisatie .
Afhangkelijk van de gekozen methode geldt voor :
Eliminatie : Behalve feitelijke plaatsing is van belang nu te
zeggen wat als akseptabel maximum aantal deelnemers
(poulegrote=maxp) wordt gezien en
wat is het minimum aantal deelnemers (=mine) mag zijn .
Het minimum bepaald wanneer Eliminatie overgaat in een
Halve kompetie systeem . Het maximum bepaald wanneer er
meerdere poules moeten worden gemaakt .
Dus Eliminatie heeft twee parameters (maxp , mine) .
Het aantal nieuw tevormen Toewijzing (=poules) is
aantalSplits = (aantal_deelnemers + maxp -1 ) / maxp .
Hierin is het aantal_deelnemers de omvang van de
verzameling Toewijzing.Organisatiedeelnemers .
(v.b. NWOC geeft aan voor districtkampioenschappen
een min van 3 en een max van oneindig .
Ik zelf adviseer min 6 en max 32 .)
Ofschoon mij geen toepassingen bekent zijn van het
splitsen van Eliminatie systemen (waarschijnlijk omdat
dit gedaan kan worden via poul_ind en zoniet omdat grote
poules geld in het laatje brengen) kan zodra dit wenselijk
is met onderstaande methode voor worden gebruikt .
Halve kompetie : Een halve kompetitie systeem bestaat uit plaatsing in
n voorronde-poules gevolgd door een finale systeem waarin
de nummers 1,2 (uit de voorronden) worden geplaatst .
Hierbij moet ook gekozen worden voor een maximum aantal
deelnemers (=maxp). Tevens moet gekozen worden voor de
maximale voorronde grote (=maxv) .
Dus Halvekompetitie heeft twee parameters (maxp , maxv) .
(v.b. Ik kies voor gevorderden maxp=15 , maxv=5 .
Voor beginners wordt vaak maxp=6 , maxv=6 gekozen.)
Het maxp aantal is nogal afhangkelijk van het tevolgen
finale systeem . Nu geldt dat :
aantalSplits = ( aantal_deelnemers + maxp - 1) / maxp
Hierin is het aantal_deelnemers de omvang van de
verzameling Toewijzing.Organisatiedeelnemers .
Het idee is dat bij een niet gesplitste poule worden de
deelnemers op een afstand van maxv gezet .
In een gesplitste poule wordt de deelnemers een afstand
aantalSplits vanelkaar gezet . De achtergrond hiervan
is dat bij een gesplitste poule de deelnemers van een
Organisatie mogelijk in twee verschillende poules komen .
De Poule_splitsing vindt dus alleen plaats als de waarde van aantalSplits
groter 1 is . Het Poule_splitsing deel kan dus de verzameling Indelingen en
Toewijzing vergroten en na gewichtwijzigen(ompouling) ook weer zich verkleinen .
Overigens kan men dit splitsen van poules meestal voorkomen door
de Poule_indeling te preziseren.
In de volgende rekenmethode is gevraagt meerdere verzameling p temaken
waarvan de elementen een element aanwijzen in de verzameling
Organisatiedeelnemers .
Dit geeft volgende voorbeelden :
maxp=3 , aantalSplit = 3
d = 1 2 3 4 5 6 7 8 9
p = |1 4 7|2 5 8|3 6 9| (DUS dit geeft drie poules)
maxp=5 , aantalSplit = 2
d = 1 2 3 4 5 6 7 8 9
p = |1 3 5 7 9|2 4 6 8| (DUS dit geeft twee poules)
Nu moet de geSplitste poule worden geplaatst op de
wedstrijd volgorde als v.b.: (zie Poule_plaatsing)
maxv=3 , maxp=5 , aantalSplit = 2
d = 1 2 3 4 5 6 7 8 9
p1= |1 3 5 7 9 | p2= |2 4 6 8|
a1= ||1 5 9||3 7|| a2= ||2 6||4 8||
Het idee is het transformeren van d(i) -> p(k,j) .
Waarbij k*j <> lengte Organisatiedeelnemers kan zijn . Zodat het wenselijk is
de deelnemers lijst aanvullen met lege elementen (maxp * aantalSplits)
Je zou dit kunnen schrijfen als (meer dimensionale set):
VAR p( maxp , aantalSplits) = 0
FOR i = 1 TO aantalSplits
FOR j = 1 TO maxp
p(j,i) = (j - 1) * aantalSplits + i
ROF
ROF
Alleen moet je nog de Toewijzing sets maken op grond van het aantalSplits .
Je zou dit ook kunnen schrijfen als (lineare set):
VAR p( 1 TO aantaldeelnemers ) = 0
FOR v = 1 TO aantalSplits
' dus iedere poule tel het aktuele aantal
count = 0
beginpl = (v-1) * aantalSplits + 1
eindpl = v * aantalSplits
IF eindpl > aantaldeelnemers THEN einpl=aantaldeelnemers
count = 1
p(beginpl) = v
FOR o = beginpl+1 TO eindpl
count = count + 1
p(o) = p(o-1) + aantalSplits
ROF
ROF
' update Toewijzing(poule) info met count
ROF
Het verschil in beide methoden zoals hier gebracht is dat de eerste niet
bestaande elementen (welke dus nul moeten zijn) in Organisatiedeelnemers
aanwijst . Terwijl de tweede methode een nul element aanwijst in de
Organisatiedeelnemer welke dus ook als leeg moet worden gezien . Men kan
zowel de ene als ook de andere benadering schrijven voor beide vormen van
set behandeling .
De Poule_mat indeling is afhankelijk van volgende elementen.
a: doorpoulebaar(altijd kunnen overpoulen) of
niet doorpoulebaar(te zwaar gaat u maar) .
b: jongens meisjes poule's aldan niet scheiden (per blok of mat).
c: blok_tyd voor alle matten (=tydblokken) of blok_tyd per mat (=doorlopend)
dit bepaald de prijsuitrijking (per blok of doorlopend) .
d: scheiding opgrond van mat afmeting (2 min 25 m2 , 3 min 36 m2 , 4 >= 49 m2)
e: tyd wensen deelnemers(i.v.m. vervoer e.d.).Dit lijdt tot tegenstrijdigheid.
Wenselijk is onder alle omstandigheden de wedstrijdtyd per mat/blok indien
meer dan een poule op de mat gepland zijn gelijk te houden .
De gewenste eisen geven een ordening in de verzameling Indelingen .
Mogelijk probleem hierbij is de wens finales op afzonderlijke tijdstippen
te spelen dit i.v.m. de ordening .
Het is nu de opdracht om zoveel mogelijk elementen uit de geordende set
Indelingen toe tewijzen aan k matten in een minimale tyd .
Het probleem is om n ongelijke luciferstokjes te leggen in k rijen zodanig
dat de rijen allen evenlang(bij benadering) worden . Het zal duidelijk zijn
dat de lengte van een rij de tyd voorsteld en het aantal rijen het aantal
te legen matten . Het maximale (niet berijkbare) optimum in het minimum van
de te leggen matten is de som van de Poul_hoofd.wedstrijdduur te delen op
de beschikbare (dag)tijd . Oftewel de totale lengte van de luciferstokjes
delen door max gewenste rij lengte . Probeer nu alle stokjes teleggen zonder
ze te breken .
De Poule_plaatsing bestaat uit de systemen n.l. Eliminatie , HalveKompetitie.
In bijde gevallen wordt uitgegaan van een geordende lijst Organisatie welke
bevat een lijst deelnemers { org { deelnemers }.. }.. .
Bij het afbeelden is de hoofdregel die dat de kans , dat deelnemers van de
zelfde Organisatie tegen elkaar tegenkomen , minimaal is .
Eliminatie : Er moet van uitgegaan worden dat de verzameling te
plaatsen deelnemers een macht van 2 is . (Zoniet vul deze
op met lege elementen) De afstand tussen twee opeen
volgende deelnemers is nu de helft van het totaal . Dat wil
houdt in dat de te verkregen plaatsings lijst symetrisch is
, dus als de helft bepaald is is de andere helft bekend .
Bovendien bevat de ene helft de even genummerde deelnemers
en de andere de oneven . Bepalen we nu de even reeks .
Voor 4 deelnemers is deze 0 2
| |
Voor 8 deelnemers is deze 0 4 2 6
| | | | (*2)
Voor 16 deelnemers is deze 0 8 4 12 2 10 6 14
| | | |___|__|___|__|
| | |______|__|___|
| |_________|__| (+2)
etc. |____________|
In rekenkundige termen geldt nu : (min deelnemers is 4)
VAR p(1 TO deelnemers) = 0
iteratie = 2LOG(deelnemers/2) , p(1)=0 , afstand=1
FOR i=1 TO iteratie
FOR l=1 TO afstand
p(l)=p(l)*2 , p(l+afstand)=p(l)+2
ROF
afstand=afstand * 2
ROF
' verdubbel de rij en maak het oneven deel en plak dit vast
' aan het reeds bestaande even deel .
FOR i=1 TO deelnemers/2
p(i+deelnemers/2)=p(i)+1
ROF
' Het maakt niet uit of je het even/oneven deel verwisseld
' p(i) bevat nu de deelnemer (referentie) terwijl de
' volgorde van p die volgorde op het wedstrijd formulier is.
Halve kompetitie :Gegeven moet zijn de (voorronde) poulegrote (=maxv) .
Tevens de lijst p welke de geordende org met deelnemers
bevat zoals in onderstaand v.b. is getoond .
maxv=3 , maxp=5
d = |1 3 5 7 9 | Dit moet een plaatsing :
p = ||1 5 9||3 7|| geven (dus een voorronde bestaande
uit een poule van 3 en een van 2 ). Ook hier gaan we uit
van een set p waarvan de elementen een element aanwijst
in de verzameling Organisatiedeelnemers .
Je zou dit kunnen schrijven als (meer dimensionale set):
aantalVoorRo = (maxp + maxv - 1)/ maxv
VAR p( maxv , aantalVoorRo) = 0
FOR i = 1 TO aantalVoorRo
FOR j = 1 TO maxv
p(j,i) = (j - 1) * aantalVoorRo + i
ROF
ROF
Je zou dit ook kunnen schrijven als (linieare set):
VAR p(1 TO deelnemers) = 0
aantalVoorRo = (maxp + maxv - 1)/ maxv{2}
FOR v = 1 TO aantalVoorRo {1->2}
'dit is 1 voorronde afbeelding
beginpl = (v-1) * aantalVoorRo + 1 {1,4}
eindpl = v * aantalVoorRo {3,6}
IF eindpl > maxp THEN einpl=maxp {3,5}
p(beginpl) = v {p(1)=1,p(4)=2
FOR o = beginpl+1 TO eindpl {2->3,5->5}
p(o) = p(o-1) + aantalVoorRo {p(2)=3 p(3)=5,
ROF p(4)=2 p(5)=4}
ROF
In de Poule_afbeelding is het de bedoeling een afdruk op papier temaken
van de geplaatste poule . Voor een Eliminatie systeem moet er om worden
gedacht dat de rust perioden tussen de wedstrijden van een kandidaat zo
maximaal mogelijk zijn . Ten tweede moet de wedstrijd volgorde zo worden
opgesteld dat de kans dat een deelnemer dezelfde deelnemer nog eens ontmoet
zou klein mogelijk is . Idem voor de winnaars ronde geldt dat de kans dat
een deelnemer een deelnemer ontmoet van de eigen organisatie zou klein
mogelijk is . Men kan dit het eenvoudigst berekenen door een ronde patroon
temaken en daarin bijde kriteria teberekenen . Eenmaal gedaan dan ligt het
grond patroon vast en kunnen de veranderingen t.g.v. poule grote het
eenvoudigst worden ingebracht m.b.v. een beslissing boom .
(Let wel de voorbeelden gegeven in het Bondsvademecum voldoen in de meeste
gevallen niet aan deze eisen .)
(Die in het Wedstrijd administratie boek ook niet.)
In afbeelding van de Halve kompetie zitten weinig problemen .
Volgorde van voorronden is niet belangrijk . Er zou alleen rekening moeten
worden gehouden met het feit dat als twee deelnemers behorend tot dezelfde
Organisatie deze in de eerste wedstrijd moeten worden gezet .
Finales blijft een probleem daar dit afhangt van de zinswijze van de
tournooi organisatie .
Resultaten moeten worden toegevoegd aan het Poule_hoofd .
Om te bepalen welke Organisatie de beste resultaten heeft behaald het
volgende algoritme . Bepaal daartoe de kans dat een deelnemer een prijs
kan winnen (ga praktisch uit van de nummers 1 en 2) :
kans = totaal_aantal_deelnemers / aantal_poules * 2 .
De nominale norm voor een organisatie zou dan moeten zijn :
norm = aantal_deelnemers_organisatie * kans .
Het succes van de organisatie wordt bepaald door :
succes = aantal_winnaars(alleen 1 en 2) - norm
De meest succesvolle organisatie wordt nu bepaald door de hoogste in rang
orde van alle organisatie . Deze methode voorkomt de dat het succes wordt
bepaald door het aantal deelnemers van een organisatie .
Ten Slotte :
Implementatie van de aangegeven algoritmen is nogal afhangelijk van
de gewenste optimalisatie en de mogelijkheden die de tegebruiken taal bied.
B.v. lijsten en set worden het makelijkst in SMALLTALK (of LISP , LOGO )
gemaakt . Terwijl variable records (Bestands definitie's) beter in ADA of
OBERON (of Pascal 7.0 , C++) kunnen worden aangegeven . Dynamische array
werken het best in QBASIC en FORTRAN . Een heel ander probleem is
portebility (overdraagbaarheid) dit bepaald de levensduur (onderhoudbaarheid)
van het programma . Ofschoon ieder verwacht dat dit ADA zal worden blijkt
voorlopig nog dat in praktijk slechts door twee talen wordt berijkt , teweten
FORTRAN en COBOL(met of zonder SQL) .
Hoe overdraagbaarder de taal teslechter de USER_INTERFACE . Een mogelijke
oplossing is door de kern (90%) in een overdraagbare taal teschrijven en
daaromheen een USER_INTERFACE per platform te maken. (V.b. hiervan is SPICE )
In verband met voorgenoemde overdrachbaarheid is het wenselijk de DATA
bestanden in FLAT ascii te porteren .