Ik hoop dat er hier slimme mensen rond lopen die mij kunnen helpen met een probleem.
Op een spelletjes site, www.turnbasedbordspellen.nl, ben ik de toernooi organisator. Het gaat hier om bordspellen die digitaal te spelen zijn.
Nou ben ik bezig met een toernooi voor een spel, waarbij je met z'n 4-en in 1 speelt. Voor dit toernooi hebben zich 20 mensen aangemeld. Ik wilde eigenlijk 2 poules van 10 maken waarin iedereen 2x tegen iedereen speelt. In 1 spel speel je tegen 3 anderen, dus met 6 spelletjes per persoon zou je tegen iedereen 2x gespeeld moeten kunnen hebben. Nou probeer ik hier een schema voor te maken. Maar ik kom er niet uit en hoopte dat iemand hier wellicht een briljante ingeving had. Of is dit simpelweg trial and error?
Competitie schema probleem
Re: Competitie schema probleem
Meestal lossen we dit soort problemen op door (systematisch) zoeken.
Een mogelijke oplossing (spelers genummerd van 1 t/m 10):
(1, 2, 3, 4 )
(1, 2, 5, 8 )
(1, 3, 6, 9 )
(1, 4, 7, 10)
(1, 5, 6, 7 )
(1, 8, 9, 10)
(2, 3, 5, 10)
(2, 4, 6, 9 )
(2, 6, 7, 8 )
(2, 7, 9, 10)
(3, 4, 7, 8 )
(3, 5, 7, 9 )
(3, 6, 8, 10)
(4, 5, 6, 10)
(4, 5, 8, 9 )
Dit zijn 15 wedstrijden, waarbij iedere wedstrijd gespeeld wordt met 4 spelers, iedereen 6 wedstrijden speelt, en iedereen elke andere speler precies 2 keer tegenkomt.
Een mogelijke oplossing (spelers genummerd van 1 t/m 10):
(1, 2, 3, 4 )
(1, 2, 5, 8 )
(1, 3, 6, 9 )
(1, 4, 7, 10)
(1, 5, 6, 7 )
(1, 8, 9, 10)
(2, 3, 5, 10)
(2, 4, 6, 9 )
(2, 6, 7, 8 )
(2, 7, 9, 10)
(3, 4, 7, 8 )
(3, 5, 7, 9 )
(3, 6, 8, 10)
(4, 5, 6, 10)
(4, 5, 8, 9 )
Dit zijn 15 wedstrijden, waarbij iedere wedstrijd gespeeld wordt met 4 spelers, iedereen 6 wedstrijden speelt, en iedereen elke andere speler precies 2 keer tegenkomt.
Re: Competitie schema probleem
Dank je Arie. Ik zal eerlijk zeggen dat ik 15 minuten na m'n post, zelf met enig puzzelen een oplossing had gevonden. Maar had de dagen daarvoor zonder succes gepuzzeld.
Maar er is dus niet een soort algoritme voor begrijp ik. Gewoon systematisch zoeken.
Maar er is dus niet een soort algoritme voor begrijp ik. Gewoon systematisch zoeken.
Re: Competitie schema probleem
Mooi dat het je al gelukt was !
Voor sommige toernooivormen bestaan er snelle oplossingen, zie bijvoorbeeld
http://en.wikipedia.org/wiki/Round-robin_tournament,
maar voor andere niet.
Jouw probleem is een variant van het Social Golfer Problem, zie bv paragraaf 2 van
http://cs.brown.edu/~pvh/sst.pdf,
waarbij in jouw geval de spelers elkaar niet maximaal 1 keer maar precies 2 keer tegenkomen.
Zeker als er ook nog aanvullende eisen (constraints) bij komen zullen we in eerste instantie terugvallen op heuristische zoekmethoden uit de informatica, zie bv
http://nl.wikipedia.org/wiki/Zoekalgoritme,
die in redelijke tijd een redelijke oplossing geven.
Voor sommige toernooivormen bestaan er snelle oplossingen, zie bijvoorbeeld
http://en.wikipedia.org/wiki/Round-robin_tournament,
maar voor andere niet.
Jouw probleem is een variant van het Social Golfer Problem, zie bv paragraaf 2 van
http://cs.brown.edu/~pvh/sst.pdf,
waarbij in jouw geval de spelers elkaar niet maximaal 1 keer maar precies 2 keer tegenkomen.
Zeker als er ook nog aanvullende eisen (constraints) bij komen zullen we in eerste instantie terugvallen op heuristische zoekmethoden uit de informatica, zie bv
http://nl.wikipedia.org/wiki/Zoekalgoritme,
die in redelijke tijd een redelijke oplossing geven.