Create a schedule for a round robin tournament with home teams in C#


[round robin]

My book Essential Algorithms, Second Edition describes an algorithm for creating a round robin schedule in detail. The following posts also explain how you can create a round robin schedule in slightly less detail.

This post explains how you can pick home and away teams for each matchup.

With an Odd Number of Teams

You could simply pick one of the teams in each of the round robin schedule’s matchups to be the home team. For example, you could let team1 be the home team if (team1 + team2 + round) % 2 == 0. That would work but it does not guarantee that every team has the same number of home games. In many sports the home team has a large advantage, so this is not a very good solution.

There’s a better approach that depends on the way we created the round robin schedule in the first place. If you have an odd number of teams, draw a polygon with that number of sides and place a team on each vertex. The following picture shows the polygon for the five teams A, B, C, D, and E.


[round robin]

Now draw horizontal lines connecting the vertices with the same Y coordinate as shown in the following picture.


[round robin]

Each of the horizontal lines defines a matchup for the round robin’s first round. Because we have an odd number of teams, there is one team at the uppermost vertex that is not matched with any other team. That team gets a bye in this round.

Now rotate the teams one position clockwise. Alternatively you can think of rotating the polygon and its horizontal lines. That’s the approach taken in Essential Algorithms. Here I’m going to rotate the teams, mostly because it’s easier to redraw the picture.

Each time you rotate the teams, the horizontal lines define a new set of matchups. If there are N teams and you rotate them N times, then the horizontal lines define N sets of matchups for the N rounds of the tournament. Each team plays every other team once and has a bye. The following picture shows the rotated teams for this example.


[round robin]

Here’s the round robin schedule for this example.

Round 1
    A has a bye
    E vs B
    D vs C
Round 2
    E has a bye
    D vs A
    C vs B
Round 3
    D has a bye
    C vs E
    B vs A
Round 4
    C has a bye
    B vs D
    A vs E
Round 5
    B has a bye
    A vs C
    E vs D

Now how do we assign a home team for each matchup? One method is to look at the horizontal lines again. During the rotations, each team visits at each end of every horizontal line exactly once. If we pick one end of each horizontal line to represent a home team, then every line defines a home team. Furthermore every team is a home team once for each horizontal line, so every team is home the same number of times.

You could simply say that the left end of each horizontal line represents a home team, but then each team will be home for several rounds in a row and then away for several rounds in a row. That might not be a problem, but it seems like it might be emotionally taxing. It might make it hard for a team to build momentum after a long string of being the away team.

To avoid that, we can alternate the directions of the horizontal lines a shown in the following picture.


[round robin]

Here the horizontal arrows point to the home team. Now as you rotate the teams through the rounds, each one alternates between being the home team and the away team. The following picture shows the round robin schedule with the home teams enclosed in brackets.

Round 1
    A has a bye
    [E] vs B
    D vs [C]
Round 2
    E has a bye
    [D] vs A
    C vs [B]
Round 3
    D has a bye
    [C] vs E
    B vs [A]
Round 4
    C has a bye
    [B] vs D
    A vs [E]
Round 5
    B has a bye
    [A] vs C
    E vs [D]

If you study the schedule you can see that each team is the home team twice. (The math also checks out. There are 10 matchups. Each team is home twice, so there are a total of 2 * 5 = 10 home teams, one for each matchup.)

With an Even Number of Teams

The method described in the previous section works if you have an odd number of teams, but it won’t work for an even number of teams. If you use a polygon with an even number of vertices, then each team ends up playing only half of the other teams and it plays them each twice.

The solution is to pull one of the teams out and make a schedule for the remaining odd number of teams. Then place the team you removed in the bye position.

Unfortunately the “bye” team always plays the team at the top of the polygon and that position has no horizontal line. That means the home and away teams are undefined for those matchups.

One solution is to simply alternate so the “bye” team is the home team half of the time. For example, if round % 2 == 0, then make the “bye” team be the home team. The following schedule shows this approach.

Round 1
    A vs [bye]
    [E] vs B
    D vs [C]
Round 2
    [E] vs bye
    [D] vs A
    C vs [B]
Round 3
    D vs [bye]
    [C] vs E
    B vs [A]
Round 4
    [C] vs bye
    [B] vs D
    A vs [E]
Round 5
    B vs [bye]
    [A] vs C
    E vs [D]

Counting Home Games

Unfortunately in this schedule the teams are no longer the home team the same number of times. Now teams A, B, and D are home two times and teams C, E, and bye are home three times.

Note also that the teams do not strictly alternate between being home and away. Some teams are home twice in a row and others are away twice in a row.

At least they are close to being home the same number of times. For example, we don’t have one team playing home six times and another team being home only twice.

The question now is, “Can we rearrange things so every team is home the same number of times?” We can answer this question with a tiny bit of simple number theory.

If we have N teams, then there are N * (N – 1) matchups. Each matchup must have a home team, so there are N * (N – 1) / 2 home slots to fill.

If the home games are evenly distributed, then each team get the same number of home slots. That can only be possible if N * (N – 1) / 2 is evenly divisible by N. Here’s where the tiny bit of number theory come in. Don’t panic! Number theory can be daunting, but in this example it’s fairly simple.

If N * (N – 1) / 2 is evenly divisible by N, that means there is some integer k such that:

    N * k = N * (N - 1) / 2

That’s just the definition of what it means for one number to be divisible by another.

If we divide both sides of the equation by N, we get the following.

    k = (N - 1) / 2

Now if N is even, then (N – 1) is odd so (N – 1) / 2 is not an integer. That means we cannot satisfy this equation if N is even. In other words, we cannot divide up the home slots evenly among the teams. In our current solution the number of times the teams are home varies by only one, so that is the best solution possible.

If N is odd, then (N – 1) is even so (N – 1) / 2 is an integer. That means the equation is satisfied so we can divide the number of home slots evenly among the teams. The earlier solution for an odd number of teams does that, so we have an ideal solution.

Conclusion

It took a while to get here, but the previous method for generating the round robin schedule also gives us a fairly simple way to assign home and away teams. Just look at the index of the horizontal lines used to generate the schedule. If a line’s index is even, make the line’s first team be the home team. If the line’s index is odd, make the line’s second team be the home team.

The new example program does that. It also counts the number of times each team is the home or away team and displays the counts in the Console window so you can verify that each time is home the correct number of times.

Download the example program and look in the GenerateRoundRobinOdd and GenerateRoundRobinEven methods to see where the program assigns the home teams.

If you find these kinds of algorithms interesting, check out my book Essential Algorithms, Second Edition. It explains a wide variety of algorithms for performing all sorts of interesting tasks including this one. (Although it doesn’t cover assigning home teams.)


Download Example   Follow me on Twitter   RSS feed   Donate




About RodStephens

Rod Stephens is a software consultant and author who has written more than 30 books and 250 magazine articles covering C#, Visual Basic, Visual Basic for Applications, Delphi, and Java.
This entry was posted in algorithms, combinatorics, mathematics and tagged , , , , , , , , , , , . Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.