Planning a competition

Question

I need to produce the schedule of a sport-event.

There are 30 teams. Each team has to play 8 matches. This means that it is not possible for each team to compete again all other teams, but I need to avoid that two team compete more than once against each other.

My idea was to generate all possible matches (for 30 teams: (30*29)/2 = 435 matches) and select from this list 120 matches (8 match for each team: 8 * 30 / 2 = 120 matches).

This is where I'm having a hard time: how can I select these 120 matches? I tried some simple solutions (take first match of the list, then the last, and so on) but they don't seem to work with 30 teams. I also tried to generate all possible match combination and find which one is working but with 30 team, this is too much calculation time.

Is there an existing algorithm that I could implement?

UPDATE

What I need to produce is a simple schedule, without elimination. Each team play 8 matchs, and that's all. At the end of the day there won't be one winner.

Each team will have his schedule, and this schedule won't change wether they win or lose. The planning is done for the whole day and is immutable.

UPDATE 2

At first, I didn't want to put too many constraints to my question, but it seems that without any constraints (other than each team not competing more than once with each other), it's just a matter of random picking 8 matchs for each team.

So here is some more details :

During this sport event, there are 6 differents sports (soccer, handball, basketball, and so on). This means there are 6 simultaneous matchs. A new round is started every 15 minutes.

Each team will have to play 8 matches, and each sport at least once.

These 6 sports are taking place at three different places. This means that during the day, each team will have to move from one place to another. These moves should be reduced as much as possible.

A team cannot play two matches in a row.

Answer 1

You could look into some already known matching approaches:

E.g. Swiss Chess system

Edit:

After reading your requirements again - that every team should play every other team exactly once, and that a winner need not necessarily be decided. It seems like a single Round Robin system would do what you want. You could just drop any extra matchups above the 8 you need.

Answer 2

It's quite simple really, just team up team i with i-4, i-3, i-2, i-1, i+1, i+2, i+3, i+4. This can be done using the algorithm below.

import java.util.*;

public class Test {

    public static void main(String[] args) {

        int TEAMS = 30, MATCHES = 8;
        int[] matchCount = new int[TEAMS];  // for a sanity check.
        List<Match> matches = new ArrayList<Match>();

        for (int team1 = 0; team1 < TEAMS; team1++)
            for (int team2 = team1 + 1; team2 <= team1 + MATCHES/2; team2++) {
                matches.add(new Match(team1, team2 % TEAMS));

                // Just for a sanity check:
                matchCount[team1]++;
                matchCount[team2 % TEAMS]++;
            }

        System.out.println(matches);

        // Sanity check:
        System.out.println(matches.size());
        System.out.println(Arrays.toString(matchCount));
    }

    static class Match {
        int team1, team2;
        public Match(int team1, int team2) {
            this.team1 = team1;
            this.team2 = team2;
        }
        public String toString() {
            return team1 + " vs " + team2;
        }
    }
}

Output:

[0 vs 1, 0 vs 2, 0 vs 3, 0 vs 4, 1 vs 2, 1 vs 3, 1 vs 4, 1 vs 5, 2 vs 3, 2 vs 4, 2 vs 5, 2 vs 6, 3 vs 4, 3 vs 5, 3 vs 6, 3 vs 7, 4 vs 5, 4 vs 6, 4 vs 7, 4 vs 8, 5 vs 6, 5 vs 7, 5 vs 8, 5 vs 9, 6 vs 7, 6 vs 8, 6 vs 9, 6 vs 10, 7 vs 8, 7 vs 9, 7 vs 10, 7 vs 11, 8 vs 9, 8 vs 10, 8 vs 11, 8 vs 12, 9 vs 10, 9 vs 11, 9 vs 12, 9 vs 13, 10 vs 11, 10 vs 12, 10 vs 13, 10 vs 14, 11 vs 12, 11 vs 13, 11 vs 14, 11 vs 15, 12 vs 13, 12 vs 14, 12 vs 15, 12 vs 16, 13 vs 14, 13 vs 15, 13 vs 16, 13 vs 17, 14 vs 15, 14 vs 16, 14 vs 17, 14 vs 18, 15 vs 16, 15 vs 17, 15 vs 18, 15 vs 19, 16 vs 17, 16 vs 18, 16 vs 19, 16 vs 20, 17 vs 18, 17 vs 19, 17 vs 20, 17 vs 21, 18 vs 19, 18 vs 20, 18 vs 21, 18 vs 22, 19 vs 20, 19 vs 21, 19 vs 22, 19 vs 23, 20 vs 21, 20 vs 22, 20 vs 23, 20 vs 24, 21 vs 22, 21 vs 23, 21 vs 24, 21 vs 25, 22 vs 23, 22 vs 24, 22 vs 25, 22 vs 26, 23 vs 24, 23 vs 25, 23 vs 26, 23 vs 27, 24 vs 25, 24 vs 26, 24 vs 27, 24 vs 28, 25 vs 26, 25 vs 27, 25 vs 28, 25 vs 29, 26 vs 27, 26 vs 28, 26 vs 29, 26 vs 0, 27 vs 28, 27 vs 29, 27 vs 0, 27 vs 1, 28 vs 29, 28 vs 0, 28 vs 1, 28 vs 2, 29 vs 0, 29 vs 1, 29 vs 2, 29 vs 3]
120
[8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8]

If you would like a more randomized setup, you could simply assign a random number between 1 and 30 to each team.

---

Update To cope with your added constraints: Let match i be of sport i mod 6.

Answer 3

Are you sure you couldn't get 32 teams :-) ?

That would make things simpler - have a standard tournament structure, but have the losers from each round play in their own chart. I think this maximises the number of teams who win at least one match during the event.

With 30 teams, you could have 2 teams play a 'friendly' and have a by in the first round. But the organisation becomes much more complicated.