CODEWITHSUNDEEP
algorithmoptimizationcombinatorics
Hannes Ovrén
Hannes Ovrén

Reputation: 21831

Match order algorithm

Background

A sports club which I am involved in asked me for help with some IT support for an upcoming competition.

The competition consists of teams of which the exact number is not necessarily known until the competition day. Hence the need for software help.

All teams will meet every other team in a number of matches. The number of matches is thus N over 2 (all combinations of 2) where N is the number of teams.

We have an unknown amount of available courts to play matches on. Likely this number will be 1 or possibly 2, but I would like a general solution.

The competition will go in turns. On each turn there will be one match played on each court.

For example, if there are two courts and five teams (A,B,C,D,E) the turn layout could look like this:

Turn      Court 1     Court 2
--------------------------------
 1        A vs B      C vs D
 2        A vs C      D vs E
 3        A vs D      B vs E
 4        B vs D      C vs E
 5        A vs E      B vs C

The problem

My problem is thus to find an algorithm to generate a set of turns that obey the following simple rules:

  1. All teams must meet all other teams exactly once during the competition.
  2. A team can not play two matches at the same turn (i.e. it can not play simultaneously on Court 1 and 2)
  3. The turns a particular team plays in should be spread out over the entire competition.

Rule 3 in detail

Rules 1 and 2 are quite easy, and I already have a solution for this. It is rule 3 that gives me problems. I'll try to show what it means:

Let's say I have 5 teams (as above) but only 1 court. There are 10 matches over 10 turns. One possible layout is 

Turn   Court 1
 1     A vs B
 2     A vs C
 3     A vs D
 4     A vs E
 5       .
 .       .
 .       .
 10      .

In this case A plays the first four matches which is not fair since they have no chance to recover their energies between games. This is what I want to avoid.

Ideas?

Upvotes: 4

Views: 265

Answers (2)

micans
micans

Reputation: 1106

A lazy approach is to use your current solution, then randomise the time slots (the rows in your presentation) X times while keeping track of some fatigure criterion and storing the best solution found so far. With other solutions you will need to be careful that you can utilise all courts fully.

Upvotes: 1

Milan
Milan

Reputation: 15849

How about a simple greedy solution where you have a fatigue value for every team.

At first, the fatigue for all the teams is set to 0. At the turn nr 1 perform an initial match up for the different courts and set the fatigue value for those teams the same value as the current turn (1 in first match up) .

In turn nr 2 pick the teams with lowest fatigue (by keeping teams in e.g priority queue) that have not played vs each other and match them. Set the fatigue value to the current turns value.

With your example, you would get:

Turn     Court 1   Team:fatigue
0           -      A:0 B:0 C:0 D:0 E:0
1        A vs B    C:0 D:0 E:0 A:1 B:1
2        C vs D    E:0 A:1 B:1 C:2 D:2
3        E vs A    B:1 C:2 D:2 E:3 A:3
4        B vs C    D:2 E:3 A:3 B:4 C:4
5        D vs E    A:3 B:4 C:4 D:5 E:5
6        A vs C    B:4 D:5 E:5 A:6 C:6 // Dont match A with B since they already played, jump to team C
.

Keeping the fresh teams always at the start. Since you probably wont have more than 100 teams, this should suffice.

Upvotes: 5

Related Questions