Hi,
Naar aanleiding van een discussie over groepsindelingen op de BK wedstrijd in Diest ben ik wat verder gaan nadenken over eerlijke groepsindelingen voor zo'n wedstrijd. Voor mij maakt het allemaal niets uit tegen wie ik vlieg, ik ben absoluut beginner, ik kom gewoon vliegen omdat ik dat leuk vind en heb geen
interesse in klasseringen en dergelijke. Maar zo'n probleem van verdelingen vind ik wel leuk. Bijna zo leuk als gaan vliegen
Ik kwam dus tot de volgende voorwaarden voor eerlijke verdelingen:
- het aantal keer dat twee piloten samen in een groep zitten moet best zo klein mogelijk zijn
- elke piloot zou best minstens 1 keer tegen elke andere piloot moeten vliegen
Wanneer aan deze eisen voldaan is, kan je nog wat strenger worden,
maar dan wordt de kost-functie die je moet gaan gebruiken nogal zwaar.
Ik heb een aantal programma's gemaakt:
- volledig willekeurige verdeling
- gewogen willekeurige verdeling waarbij de voorkeur gegeven wordt aan
piloten met het laagste aantal 'duels' binnen een groep
- verdeling via 'simulated annealing', een heuristiek die het toelaat
om vrij snel een minimum te vinden voor een gegeven kost functie
Volledig willekeurig is wat er gebruikt werd in Diest denk ik, en ook
in het programma f3kscore. Ik had f3kscore eens gebruikt voor 19 piloten en 6 taken zoals in Diest en dat gaf een gelijkaardige verdeling waarbij 11 keer
4 duels voorkwamen. Met willekeurig zoeken moet je dus wel wat geluk
hebben om een goede verdeling te vinden. Er zijn heel wat combinaties
(zie Combinatorics: Permutations, Combinations, Factorial, Exponents Generate voor de Wiskunde):
- een eerste groep van 7 piloten kiezen uit 19 kan op: 19! / (19-7)! / 7! = 50388 manieren
- een tweede groep van 7 uit de 12 overgebelven kan op: 12! / (12-6)! / 6! = 932 manieren
- de laatste 6 liggen dan vast
Dus het kiezen van 3 groepen van respectievelijk 7, 6 en 6 piloten uit
19 kan op 46558512 manieren. Daaruit moet je er dan 6 kiezen en die 6
samen moeten dan voldoen aan de bovenstaande eisen. Je hebt dan maar
liefst te kiezen uit, wel ja, gigagantisch veel combinaties:
10185782809431273506508475902488405938661393280.
Daar komen we niet uit voor de volgende wedstrijd ;-)
Een gewogen willekeurige verdeling kan al wat helpen. Maar nog steeds
moet je wat geluk hebben. En je kent dat van de Lotto, meestal win je
maar 2,5 euro.
Dan maar wat meer Wiskunde er bij gesleurd, en vertrekkende van een
willekeurige oplossing 'simulated annealing' zijn werk laten doen
(Simulated annealing - Wikipedia). Hiermee heb je
binnen enkele minuten een behoorlijke oplossing. Voor Diest zou geen
enkele piloot 4 keer tegen een andere moeten uitkomen, en in de
oplossingen die ik gevonden heb zijn er heel weinig piloten die nooit
tegen mekaar uitkomen.
Hier vindt je de resultaten van de berekeningen voor wedstrijden van 5 tot 50 piloten, en van 5 to 20 rondes: F3K Contests
(even niet op de URL letten, ik beheer die site en het was de enige waar ik al de data kwijt kon)
Op die pagina zie je de resultaten voor een aantal optimisaties die ik gedaan heb: worst-case, willekeurig en met simulated annealing. In de tabel kies je het aantal piloten, het aantal groepen en het aantal rondes. Dan kan je doorklikken naar de resultaten voor die wedstrijd. Bijvoorbeeld voor Diest was dit 19 piloten in drie groepen (7+6+6) en 6 rondes:
F3K Contests
Het leuke is ook dat je die resultaten nooit meer moet herberekenen. Vertrekkende van de groepsindelingens die je daar vindt kan je je wedstrijd gaan organiseren. Je kan de lijst met piloten voor elke wedstrijd anders mappen op de op de nummers die je op de site vindt, of de volgorde van de groepen binnen een ronde steeds anders kiezen. Er staat een link op naar een XML bestand dat je daarvoor kan gebruiken.
Ok. Ik heb me even laten gaan. Nerd factor 23 vrees ik. Kan je daar nu
wat mee aan? Meer piloten of andere groepsindelingen? Ander bestandsformaat? Opmerkingen, suggesties, ... Je laat maar weten.
Groetjes,
Jos.
Naar aanleiding van een discussie over groepsindelingen op de BK wedstrijd in Diest ben ik wat verder gaan nadenken over eerlijke groepsindelingen voor zo'n wedstrijd. Voor mij maakt het allemaal niets uit tegen wie ik vlieg, ik ben absoluut beginner, ik kom gewoon vliegen omdat ik dat leuk vind en heb geen
interesse in klasseringen en dergelijke. Maar zo'n probleem van verdelingen vind ik wel leuk. Bijna zo leuk als gaan vliegen
Ik kwam dus tot de volgende voorwaarden voor eerlijke verdelingen:
- het aantal keer dat twee piloten samen in een groep zitten moet best zo klein mogelijk zijn
- elke piloot zou best minstens 1 keer tegen elke andere piloot moeten vliegen
Wanneer aan deze eisen voldaan is, kan je nog wat strenger worden,
maar dan wordt de kost-functie die je moet gaan gebruiken nogal zwaar.
Ik heb een aantal programma's gemaakt:
- volledig willekeurige verdeling
- gewogen willekeurige verdeling waarbij de voorkeur gegeven wordt aan
piloten met het laagste aantal 'duels' binnen een groep
- verdeling via 'simulated annealing', een heuristiek die het toelaat
om vrij snel een minimum te vinden voor een gegeven kost functie
Volledig willekeurig is wat er gebruikt werd in Diest denk ik, en ook
in het programma f3kscore. Ik had f3kscore eens gebruikt voor 19 piloten en 6 taken zoals in Diest en dat gaf een gelijkaardige verdeling waarbij 11 keer
4 duels voorkwamen. Met willekeurig zoeken moet je dus wel wat geluk
hebben om een goede verdeling te vinden. Er zijn heel wat combinaties
(zie Combinatorics: Permutations, Combinations, Factorial, Exponents Generate voor de Wiskunde):
- een eerste groep van 7 piloten kiezen uit 19 kan op: 19! / (19-7)! / 7! = 50388 manieren
- een tweede groep van 7 uit de 12 overgebelven kan op: 12! / (12-6)! / 6! = 932 manieren
- de laatste 6 liggen dan vast
Dus het kiezen van 3 groepen van respectievelijk 7, 6 en 6 piloten uit
19 kan op 46558512 manieren. Daaruit moet je er dan 6 kiezen en die 6
samen moeten dan voldoen aan de bovenstaande eisen. Je hebt dan maar
liefst te kiezen uit, wel ja, gigagantisch veel combinaties:
10185782809431273506508475902488405938661393280.
Daar komen we niet uit voor de volgende wedstrijd ;-)
Een gewogen willekeurige verdeling kan al wat helpen. Maar nog steeds
moet je wat geluk hebben. En je kent dat van de Lotto, meestal win je
maar 2,5 euro.
Dan maar wat meer Wiskunde er bij gesleurd, en vertrekkende van een
willekeurige oplossing 'simulated annealing' zijn werk laten doen
(Simulated annealing - Wikipedia). Hiermee heb je
binnen enkele minuten een behoorlijke oplossing. Voor Diest zou geen
enkele piloot 4 keer tegen een andere moeten uitkomen, en in de
oplossingen die ik gevonden heb zijn er heel weinig piloten die nooit
tegen mekaar uitkomen.
Hier vindt je de resultaten van de berekeningen voor wedstrijden van 5 tot 50 piloten, en van 5 to 20 rondes: F3K Contests
(even niet op de URL letten, ik beheer die site en het was de enige waar ik al de data kwijt kon)
Op die pagina zie je de resultaten voor een aantal optimisaties die ik gedaan heb: worst-case, willekeurig en met simulated annealing. In de tabel kies je het aantal piloten, het aantal groepen en het aantal rondes. Dan kan je doorklikken naar de resultaten voor die wedstrijd. Bijvoorbeeld voor Diest was dit 19 piloten in drie groepen (7+6+6) en 6 rondes:
F3K Contests
Het leuke is ook dat je die resultaten nooit meer moet herberekenen. Vertrekkende van de groepsindelingens die je daar vindt kan je je wedstrijd gaan organiseren. Je kan de lijst met piloten voor elke wedstrijd anders mappen op de op de nummers die je op de site vindt, of de volgorde van de groepen binnen een ronde steeds anders kiezen. Er staat een link op naar een XML bestand dat je daarvoor kan gebruiken.
Ok. Ik heb me even laten gaan. Nerd factor 23 vrees ik. Kan je daar nu
wat mee aan? Meer piloten of andere groepsindelingen? Ander bestandsformaat? Opmerkingen, suggesties, ... Je laat maar weten.
Groetjes,
Jos.
