Circle method scheduling algorithm for a round robin tournament with an uneven number of teams

combinatorics

I am creating a software library for creating round robin tournaments where each team plays every other team one time. However, I am struggling with sorting the games for an uneven number of teams.

I implemented the scheduling algorithm found on the wikipedia page for Round-robin tournament referred to as the circle method. Here is an example of how that algorithm works where each column is a "game" if we have a set of teams 1 2 3 4.

1 2
4 3

1 4
3 2

1 3
2 4

The 1 is kept in place and the rest of the teams are rotated around n-1 times where n is number of teams.

However, this can not be done with an uneven number of teams as even a simple example such as 1 2 3 fails because it misses 1 match where 2 faces 3.

1 2
3

1 3
2

Using a simple loop I can generate all the games for any given number of teams. The following is written in Golang but I hope it is easy enough to understand. 

// teams2 is a copy of teams
teams2 := teams
// I loop through a full set of team
for _, t := range teams {
    // for every iteration we remove the first team in team2
    teams2 = teams2[1:]
    // I loop through the subset of teams which does not include the current team t or any previous team t
    for _, t2 := range teams2 {
        // Here I print the match
        fmt.Printf("%d:%d\n", t, t2)
    }
}

That code will give the following output for 1 2 3 which includes all possible combinations.

1:2
1:3
2:3

However, the problem is that it is not ordered according to the Scheduling algorithm I mentioned earlier. The first game should be 1:3 and not 1:2. The sorting of games gets even worse with a larger set of teams such as 9 or 11.

How can I create a scheduling algorithm for an uneven number of teams in a round robin tournament which works as closely as possible to the circle method for an even number of teams?

Best Answer

Suppose you have an odd number $n$ of players. Add an extra player $n+1$, and apply the circle scheduling algorithm to generate a round robin for $n+1$ players. Whoever plays against player $n+1$ sits still that round.

You get the nicest solution if player $n+1$ is the one that stays at the same spot.

Related Question