Algorithm for a round robin based tournament with a specific amount of matches per round

algorithms

I'm currently trying to create a system for a specific tournament but I can't figure out how to generate the matches table.

I have a tournament with <T> teams.
Each team needs to play vs each other team exactly once.

The tournament location has <M> fields which can be played on at the same time (Therefore limiting the amount of matches per round to <M>).

One of the solutions I know of is a round robin tournament.

The two solutions on wikipedia however only show solutions for <T> / 2 matches/fields which is not what I want.

I want that the amount of matches played at the same time is variable based on the input (tournament location).

Obvioulsy there can be rounds where specific teams are not playing. But the algorithm should always return the smallest number of rounds possible.

What's the best way to solve this problem or are there any efficient algorithms for that?

To clarify: Each match/round takes the same amount of time and each match/round starts at the same time.

Edit: Here's an example:

I have 6 teams:

When we apply the round robin algorithm it'd generate a table like this:

         Field/Match 1 Field/Match 2 Field/Match 3
Round 1: 1 vs 6     2 vs 5     3 vs 4
Round 2: 1 vs 5     6 vs 4     2 vs 3
Round 3: 1 vs 4     5 vs 3     6 vs 2
Round 4: 1 vs 3     4 vs 2     5 vs 6
Round 5: 1 vs 2     3 vs 6     4 vs 5

Now I'm at a tournament location with only 2 fields available, therefore only 2 matches can be played at the same time.

The easiest way to alter this table would be to append all fields which don't exist to the end of the tournament:

         Match 1    Match 2
Round 1: 1 vs 6     2 vs 5
Round 2: 1 vs 5     6 vs 4
Round 3: 1 vs 4     5 vs 3
Round 4: 1 vs 3     4 vs 2
Round 5: 1 vs 2     3 vs 6
Round 6: 3 vs 4
Round 7: 2 vs 3
Round 8: 6 vs 2
Round 9: 5 vs 6
Round 10: 4 vs 5

This however wouldn't be optimal since field 2 wouldn't be used at all.

I need an algorithm which generates a good solution with optimizes all available fields.

Example of an table with optimally used fields:

         Match 1    Match 2
Round 1: 1 vs 6     2 vs 5
Round 2: 1 vs 5     6 vs 4
Round 3: 1 vs 4     5 vs 3
Round 4: 1 vs 3     4 vs 2
Round 5: 1 vs 2     3 vs 6
Round 6: 3 vs 4     6 vs 2
Round 7: 2 vs 3     5 vs 6
Round 8: 4 vs 5

And I don't know how I could convert this to an algorithm which works with any amount of matches/fields per round.

Best Answer

You're on the right track. I think using a queue should help you out. I'd do something like this:

List<Team> allTeams = getAllTeams(); // Returns the list of all teams
List<Match> allMatches = getAllMatches(allTeams); // Generate all combos of teams - should be n^2 matches
List<Field> allFields = getAllFields(); // Return the list of all possible fields
Queue<Match> remainingMatches(allMatches); // A queue of all the remaining matches - starts with all of them
List<Match, Field> matchesToBePlayed; // initially empty
while (remaininMatches.size() > 0)
{
    Field nextField = getNextAvailableField(allFields);
    if (nextField == NULL)
    {
        // Play all the matches we have
        playMatches(matchesToBePlayed);
        matchesToBePlayed.clear(); // reset it when they've been played
    }
    else
    {
        Match nextMatch = remainingMatches.front();
        remainingMatches.pop_front();
        matchesToBePlayed.addMatch(nextField, nextMatch);
    }
}

So you simply queue up all the available matches. Then you sit in a loop and get the next available field, and the next available match and assign the match to the field. When you're out of fields, you can sleep until a match ends. Since they all end at the same time, you aren't missing anything. When a match ends, A field becomes available.

This assumes a few things:

  1. The allMatches list is sorted so that you never end up with a team in 2 matches at the same time. There are other ways you could do this such as checking the nextMatch variable to ensure that none of the teams involved are already playing.
  2. The Field object has a flag saying it's in use and getNextAvailableField() walks the list of fields and pulls out the next one that doesn't have the inUse flag set. Or perhaps the list of all fields internally keeps 2 lists so you don't have to walk them.
Related Topic