Matching Algorithm

Question

Background

The sports club in which I participate asked me for help in supporting IT for the upcoming contest.

The competition consists of teams of which the exact number is not necessarily known until the day of the competition. Consequently, the need for software support.

All teams will meet with each team. in the number of matches . Thus, the number of matches is N more than 2 (all combinations of 2), where N is the number of teams.

We have an unknown number of ships available to play matches. This number will probably be 1 or maybe 2, but I would like a general solution.

The competition will be held in revs . At each turn , one match will be held in each court .

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

  Turn Court 1 Court 2
 --------------------------------
  1 A vs BC vs D
  2 A vs CD vs E
  3 A vs DB vs E
  4 B vs DC vs E
  5 A vs EB vs C

Problem

My problem is to find an algorithm for generating a lot of turns that obey the following simple rules:

• All teams must meet with all other teams exactly once during the competition.
• A team cannot play two matches in the same move (i.e., it cannot play simultaneously in court 1 and 2).
• The turns that a particular team plays must be distributed throughout the competition.

Detailed Rule 3

Rules 1 and 2 are pretty simple, and I already have a solution for this. This rule 3 gives me problems. I will try to show what this means:

Let's say I have 5 teams (as indicated above), but only 1 court. There are 10 matches in 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 .
  .  .
  .  .
  ten .

In this case, A plays the first four matches, which are not fair, since they have no chance to restore their energy between games. I want to avoid that.

Ideas?

Answer 1

How about a simple greedy decision where you have a fatigue value for each team.

First, the fatigue for all teams is 0. On the turn nr 1, make the initial match for different vessels and set the fatigue value for these teams to the same value as the current turn (1 in the first match).

In turn, nr 2 select teams with minimal fatigue (holding teams, for example, a priority queue) that did not play against each other and did not correspond to them. Set the fatigue value to the current rpm value.

In your example, you will get:

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

Saving new teams is always at the beginning. Since you probably won't have more than 100 teams, this should be enough.

Answer 2

The Len approach is to use your current solution and then randomize the time intervals (lines in the presentation) X times, tracking some obsolescence criteria and preserving the best solution found so far. In other decisions, you need to be careful to make full use of all courts.