2

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.

  • 1
    Do all matches in a round start at the same time and take the same amount of time? – user1118321 Feb 4 '18 at 18:18
  • Yes every round starts at the same time and takes the same amount of time. – Lyze Feb 4 '18 at 18:22
  • I'm a little confused about what you're confused about. Let's say you have 20 teams, so there would potentially be 10 matches initially. You're at a location with 5 fields. What do you want to happen? Only 5 of the 10 matches will be played? Or do you want the first 5 to be played, then when those are over, the remaining 5 will be played? – user1118321 Feb 4 '18 at 18:54
  • I've updated the post with an example on what should happen when there are more teams then fields available for the round robin algorithm. – Lyze Feb 4 '18 at 19:06
  • And yeah that's what I basically want @user1118321 . The matches which can't be played due to field limitations should be appended at the end of the tournament but so that it doesn't waste fields/rounds. (see example) – Lyze Feb 4 '18 at 19:58
1

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.