[alg] competitie algoritme knvb

[rewind.]

Om tijd te besparen en niet alle wedstrijden handmatig in te voeren wil ik een functie maken die een wedstrijdschema genereerd net zoals de knvb dat doet.

Stel er zijn 6 teams. Bij de knvb ontstaat er het volgende schema:

code:

Ronde   Thuisteam   Uitteam
1       1           6
1       2           5
1       3           4
2       4           2
2       5           1
2       6           3
3       1           4
3       2           3
3       5           6
4       2           6
4       3           1
4       4           5
5       1           2
5       5           3
5       6           4

De volgende gegevens heb ik:

aantal speelrondes = aantal teams - 1
aantal wedstrijden per ronde = aantal teams / 2

De structuur die gebruikt word snap ik en ik kan het ook zo uitschrijven op papier. Ik krijg het alleen niet voor elkaar die structuur om te zetten in een functie.

Wat me al wel is gelukt is het genereren van een wedstrijdschema met de round robin methode, deze sluit alleen niet aan bij de methode van de knvb

Kan iemand mij helpen met het maken van deze functie die aan de hand van het aantal teams een speelschema in een array/tabel propt?

[RobIII]

Ik heb de ballen (pun intended ) verstand van voetbal, competitie schema's en laat staan de KNVB. Maar wat let je om eerst eens gewoon in pseudocode uit te schrijven hoe je zo'n schema maakt en het dan in echte code om te gieten? Het lijkt me nou niet echt rocket science om dat voor elkaar te krijgen en daarnaast is je topic op deze manier wel érg scriptrequesterig...

Ik heb het niet in detail bekeken, maar zit hier niets tussen?

[ Voor 56% gewijzigd door RobIII op 01-03-2007 19:52 ]

[rewind.]

Dat is nou precies wat ik wil.. de pseudocode ontwikkelen. Ik weet hoe het schema in elkaar zit en hoe ik zo'n schema op papier maak. Ik krijg het alleen niet voor elkaar hier een goede methodiek / algoritme in te vinden. Bij de round robin methode wordt 1 team gelockt meestal het eerste team terwijl de anderen per speelronde roteren.

[edit] het is absoluut geen scriptrequest. als iemand me opweg kan helpen met de methodiek/algoritme ben ik tevreden! De code kan ik zelf wel typen

[ Voor 18% gewijzigd door rewind. op 01-03-2007 20:44 ]

[dr snuggles]

Ik zie niet direct logica in het schema hierboven. Maar als ik het knvb schema goed begrijp moet elk team een keer tegen een ander team spelen. Bij 6 teams moeten er dus 5 wedstrijden per team gespeeld worden. Als team 1 tegen 2 speelt, is dat hetzelfde als dat team 2 tegen team 1 speelt. In totaal heb je dus Nx(N-1)/2 wedstrijden, met N het aantal teams.

Als algoritme daarvoor kun je nemen:
Team 1 tegen alle andere teams (totaal 5).
Team 2 tegen alle andere teams met een nummer hoger dan 2 (totaal 4).
Team 3 tegen alle andere teams met een nummer hoger dan 3 (totaal 3).
enz.
Totaal = 5+4+3+2+1+0 = 15 wedstrijden = 6x5/2

Nu je alle wedstrijden hebt moet je nog iets maken om de wedstrijden te verdelen over N-1 rondes. Hiervoor zijn verschillende manieren en één van de manieren is die van de KNVB. Het enige waar je op moet letten is dat
• Team 1 niet tegen team 2 en 3 tegelijk moet spelen in één ronde.
• Dat elke wedstrijd maximaal 1x wordt gespeeld (en dus automatisch elke wedstrijd minimaal 1x wordt gespeeld).

[ Voor 12% gewijzigd door dr snuggles op 01-03-2007 20:50 ]

[soulrider]

kan je even in je eigen woorden zeggen hoe die tabel die je geeft gegenereerd wordt ?

dat op zich is al heel ruwe pseudo-code

en dat kan je dan veralgemenen en nadien telkens verfijnen naar echte code

anders ga je een paar voorbeelden moeten geven
(met bv ook 3,4 en 5 teams)

dan is het algoritme erachter wrs ook voor ons zo te ontravelen en in pseudo-code te noteren

(lijkt een beetje op script-request - maar is eerder alsof je een goeie zet nodig hebt in de goede richting: help ons dan effe met het omschrijven van de achterliggende logica en wie weet... mss krijg je je nodige zet )

[rewind.]

Ronde 1
Team1 speelt tegen het laatste team.
Team2 speelt tegen het één na laatste team.
Team3 speelt tegen het twee na laatste team.

Ronde 2
Team1 speelt tegen één na laatste team.
Team2 speelt tegen het twee na laatste team.
Team3 speelt tegen het drie na laatste team.

MAAR:
Bij 6 teams betekend dit:

Ronde 1
t1 - t6
t2 - t5
t3 - t4

Ronde 2
t1 - t5
t2 - t4
t3 - t6

Zoals je kan zien kan in ronde 2 t3 niet tegen t3 spelen omdat een team niet tegen zichzelf kan spelen. t1 en t2 spelen al dus moet t3 tegen t6 spelen.

Zoals je kan zien moet dus altijd bijgehouden worden welke teams er in een ronde spelen en kan een team nooit 2x of tegen elkaar spelen.


Volgens mij heb ik nu ruw de pseudo code al voor handen.

[Bolukan]

Dit werkt ook:

Ronde 1, wedstrijd 1: T1: Tx; met x = ronde + 1 (dus 2, 3, etc)
Dan voor alle wedstrijden de uit-teams bepalen via
Wedstrijd 2: x + 1
Wedstrijd 3: x + 2 etc tot de laatste wedstrijd en dan terug naar boven van de thuis-kant
Bij 10 teams, is de laatste wedstrijd dus 6 - 5

Ronde 2, volgt ook bovenstaand schema.
De laatste wedstrijd wordt dan 7-6

Als je per ronde nog de wedstrijden spiegelt (dus ronde 1: 1 thuis, ronde 2:1 uit), kom je redelijk evenwichtig uit, maar net niet helemaal optimaal.

[dr snuggles]

Ik heb nog even verder gedacht en het is vrij lastig

Er zijn twee manieren om je probleem op te lossen:
1) Subtiele weg via een algoritme
2) Brute force weg door te proberen totdat je klaar bent

1 is lastig te bedenken, maar simpel te implementeren. Bij 2 is het precies andersom.

Wat je iig nodig gaat hebben is hoeveel wedstrijden er gespeeld moeten worden, hoeveel rondes er zijn en hoeveel wedstrijden per ronde. Stel er zijn n teams:
Aantal wedstrijden = n*(n-1)/2
Aantal wedstrijden per ronde = round down (n/2)
Aantal rondes = n*(n-1)/2 / round down (n/2)

Een lekker irritant voorbeeld om dit te checken is bij n=5 teams. Hierbij zijn er volgens de formules 10 wedstrijden, met 2 wedstrijden per ronde en totaal 5 rondes. Wat ook had gekund zijn 3,3,2,2 wedstrijden = totaal 10.

[rewind.]

dr snuggles >
Bij een oneven aantal teams voeg je er gewoon een 'ghost' team aan toe, op die manier speelt alsnog iedereen tegen elkaar en degene tegen het ghostteam geplant staat speelt niet.

Bolukan >
Dat klopt! Ik had ook al een oplossing in de vorm van round-robin alleen genereerd deze een ander schema dan de knvb en het is juist van belang dat het schema hetzelfde is!

[RobIII]

Waar je naar op zoek bent is permutaties (denk ik, voor zover ik competitieschema's begrijp )

[Bolukan]

Heeft er ook nog iemand een idee hoe je het aantal uit en thuis wedstrijden tot 1 verschil kunt beperken (het is nou eenmaal een oneven aantal wedstrijden met een even aantal ploegen)

[Bolukan]

Als je de laatste wedstrijd van de even rondes tot de helft van de competitie omdraait, dan heb je een eerlijke verdeling van thuis en uit wedstrijden.
Dus bij 14 teams: Er zijn dan 13 rondes en de helft is 6,5. Van ronde 2, 4 en 6 de laatste (7e) wedstrijd omdraaien en dan gaat alles ideaal.

[rewind.]

na wat prutsen en wat hulp van een klasgenoot heb ik nu het volgende in php:

PHP:

<?php
function genTeam ($iTotalteams) {

    // deze loop geld voor de rondes
    for ($i=1; $i < $iTotalteams; $i++) {
    
        $iLast = $iTotalteams+1;
        $iFirst = 0;

        // team loop
        for ($i2=1; $i2 <= ($iTotalteams/2); $i2++) {
            if ($i2 == 1) {
                $iLast = $iLast-$i;
             } else {
                $iLast = $iLast-1;           
             }
             
            $iFirst = $iFirst+1;
            if(in_arrayr($iFirst,$arrTeam[$i])) {
                while(in_arrayr($iFirst,$arrTeam[$i])) {
                    $iFirst++;
                    if($iFirst == $iTotalteams+1) {
                        $iFirst == 1;
                    }
                }
            }
            
            $arrTeam[$i][$i2]['thuis'] = $iFirst;
            
            if(in_arrayr($iLast,$arrTeam[$i])) {
                while(in_arrayr($iLast,$arrTeam[$i])) {
                    $iLast--;
                    if($iLast == 0) {
                        $iLast = $iTotalteams;
                    } 
                }
            }
            
            $arrTeam[$i][$i2]['uit']     = $iLast;

        }   

    }
    
    return $arrTeam;
}
?>

uitvoer:

code:

Array
(
    [1] => Array
        (
            [1] => Array
                (
                    [thuis] => 1
                    [uit] => 6
                )

            [2] => Array
                (
                    [thuis] => 2
                    [uit] => 5
                )

            [3] => Array
                (
                    [thuis] => 3
                    [uit] => 4
                )

        )

    [2] => Array
        (
            [1] => Array
                (
                    [thuis] => 1
                    [uit] => 5
                )

            [2] => Array
                (
                    [thuis] => 2
                    [uit] => 4
                )

            [3] => Array
                (
                    [thuis] => 3
                    [uit] => 6
                )

        )

    [3] => Array
        (
            [1] => Array
                (
                    [thuis] => 1
                    [uit] => 4
                )

            [2] => Array
                (
                    [thuis] => 2
                    [uit] => 3
                )

            [3] => Array
                (
                    [thuis] => 5
                    [uit] => 6
                )

        )

    [4] => Array
        (
            [1] => Array
                (
                    [thuis] => 1
                    [uit] => 3
                )

            [2] => Array
                (
                    [thuis] => 2
                    [uit] => 6
                )

            [3] => Array
                (
                    [thuis] => 4
                    [uit] => 5
                )

        )

    [5] => Array
        (
            [1] => Array
                (
                    [thuis] => 1
                    [uit] => 2
                )

            [2] => Array
                (
                    [thuis] => 3
                    [uit] => 6
                )

            [3] => Array
                (
                    [thuis] => 4
                    [uit] => 5
                )

        )

)

zodra ik voor $iTotalteams 6 neem dan klopt het schema tot ronde 5 in ronde 5 gaat het bij de laatste 2 wedstrijden fout. Dit komt omdat ik dus niet controleer of een wedstrijd al wel gespeeld is of niet! Wie o wie kan mij nu vertellen hoe ik alle wedtrijden op een mooie manier met elkaar kan vergelijken?

p.s. thuis / uit verschil heb ik ook nog niet ingebakken!

[chris]

Ik heb hier de haskell-code die alle wedstrijden op de goede volgorde genereert. Moet je alleen nog zorgen dat het op de goede punten wordt opgesplitst in rondes. Het kan vast makkelijker, maar deze was leuk om te bouwen.

Haskell:

module Competitie where
import Data.List

data Wedstrijd = Wedstrijd Int Int
instance Eq Wedstrijd where 
  (Wedstrijd a b) == (Wedstrijd c d) = (a,b)==(c,d) || (a,b)==(d,c)
instance Show Wedstrijd where show (Wedstrijd a b) = show a ++ "-" ++ show b

permutaties :: Eq a => [a] -> [[a]]
permutaties [] = [[]]
permutaties xs = [x:ys | x <- xs, ys <- permutaties (delete x xs)]

-- competitie voor x teams
competitie x = take aantalWedstrijden $ nub $ alleMogelijkheden teams
 where aantalWedstrijden = (sum teams) `div` 2
       teams = [1..x]
       alleMogelijkheden = concat . map wedstrijden . permutaties
       wedstrijden [] = []
       wedstrijden (t1:t2:teams) = (Wedstrijd t1 t2):(wedstrijden teams)

Aanroepen als "competitie 6", waarbij 6 het aantal teams is.

Voorbeeld:

*Competitie> competitie 6
[1-2,3-4,5-6,3-5,4-6,3-6,4-5,1-3,2-4,2-5]

[ Voor 4% gewijzigd door chris op 02-03-2007 06:12 . Reden: Voorbeeld ]

[Verwijderd]

Stoney187 schreef op donderdag 01 maart 2007 @ 19:39:
Om tijd te besparen en niet alle wedstrijden handmatig in te voeren wil ik een functie maken die een wedstrijdschema genereerd net zoals de knvb dat doet.

Stel er zijn 6 teams. Bij de knvb ontstaat er het volgende schema:

code:

Ronde   Thuisteam   Uitteam
1       1           6
1       2           5
1       3           4
2       4           2
2       5           1
2       6           3
3       1           4
3       2           3
3       5           6
4       2           6
4       3           1
4       4           5
5       1           2
5       5           3
5       6           4

De volgende gegevens heb ik:

aantal speelrondes = aantal teams - 1
aantal wedstrijden per ronde = aantal teams / 2

De structuur die gebruikt word snap ik en ik kan het ook zo uitschrijven op papier. Ik krijg het alleen niet voor elkaar die structuur om te zetten in een functie.

Wat me al wel is gelukt is het genereren van een wedstrijdschema met de round robin methode, deze sluit alleen niet aan bij de methode van de knvb

Kan iemand mij helpen met het maken van deze functie die aan de hand van het aantal teams een speelschema in een array/tabel propt?

Dit topic is alweer een tijd oud maar het antwoord op mijn vraag zou mooi aansluiten op de startpost van de topicstarter. Aan de topicstarter wil ik vragen of hij er nog achter is gekomen op wat voor wanneer de KNVB het speelschema samenstelt. Ik ben bekend met round-robin maar ik vroeg mij ook af of dit inderdaad zo wordt toegepast door de KNVB of dat zij er achteraf modificaties op toepassen. Immers, de eredivisie kent nu ook zogeheten Super Sunday's waarbij er grote wedstrijden op een dag staan gepland.
Dit zou betekenen dat de KNVB van te voren weet op welke positie in de lijst men de betreffende clubs moet plaatsen om middels round-robin tot Super Sunday's te kunnen komen. Of de KNVB wisselt een paar wedstrijden achteraf zodat er Super Sunday's ontstaan. Het eerste lijkt me onwaarschijnlijk omdat er weinig uitgangssituaties zijn die zullen leiden tot bepaalde wedstrijden op dezelfde speeldag. Daarnast moet het in de praktijk ook nog maar uitvoerbaar zijn.
De tweede optie lijkt mij waarschijnlijker...

Topicstarter, heb jij na een jaar nog veel meer inzichten hierin verkregen?