Planning a competition_问答_开发者_运维开发者技术经验分享

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 det开发者_如何学Pythonails :

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.

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.

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.

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.

I do not know of an existing implementation, but here is a possible solution for you:

Make three groups of 9 teams and pair them each with all others, so that each plays once against all others. Each of the 27 teams now plays 8 games.

Now take the remaining three teams, one for each group.

Modify some games of each team:

1-2 -> 1-10, 2-10 
3-4 -> 3-10, 4-10 
5-6 -> 5-10, 6-10 
7-8 -> 7-10, 8-10

Broker's Algorithm might work. Funnily enough I can't find a good description in the net, so I'll try to explain the system.

Effectively, each team would ask each other team for a score for a match and the matchup that scores highest is selected. This is repeated for each team and match. The resulting schedule is saved and a total score is calculated. Then with different starting points (i.e. you could just randomise the team order) this is done again and if the total score is higher, this schedule is selected instead. You repeat this until you either find a schedule yielding a high enought score or after a pre-defined number of tries.

Total score could be calculated by distance travelled by each team, the smaller the number the better. Obviously you don't pick matches that break your rules (too many matches of similar type, same teams playing each other again).

Scoring could go something like this:

If same venue for team: 100 points (i.e. if for both = 200).
For travelling between venues, score is determined for both teams depending on length, i.e. A -> B and B -> A 50 points (they are near) A -> C and C -> A 30 points (not so near) B -> C and C -> B 0 points (the travelling we want to do as little as possible).
If team hasn't played this sports yet: 100 points.
If team has played this sport once: 50 points.

Of course the problem with BA is finding good values for different parameters so you would need to spend some time finding them.

If you want a simple algorithm that will produce a schedule where teams don't play against each other more than once that is not hard with given parameters.

Here is an example for 10 teams and 5 rounds, the solution is shown as an array where if a value of schedule[i][j] is zero the teams don't play together, and if it is a number then it shows in which round they play together.

   1  2  3  4  5  6  7  8  9  10
1 [0, 5, 0, 4, 0, 3, 0, 2, 0, 1]
2 [5, 0, 4, 0, 3, 0, 2, 0, 1, 0]
3 [0, 4, 0, 3, 0, 2, 0, 1, 0, 5]
4 [4, 0, 3, 0, 2, 0, 1, 0, 5, 0]
5 [0, 3, 0, 2, 0, 1, 0, 5, 0, 4]
6 [3, 0, 2, 0, 1, 0, 5, 0, 4, 0]
7 [0, 2, 0, 1, 0, 5, 0, 4, 0, 3]
8 [2, 0, 1, 0, 5, 0, 4, 0, 3, 0]
9 [0, 1, 0, 5, 0, 4, 0, 3, 0, 2]
10[1, 0, 5, 0, 4, 0, 3, 0, 2, 0]

So from this table in first round the teams (1, 10), (2, 9), (3, 8), (4, 7), (5, 6) play, in the second round the teams (1, 8), (2, 7), (3, 6)... etc.

To produce this table the algorithm is rather trivial, here is some python code:

#!/bin/env python

def simpleNRooks(size, rounds, schedule):
    ''' Place n rooks on board so that they don't hit each other in each round,
        nor reuse the spots from previous rounds '''
    for i in range(size):
        for j in range(rounds):
            if size-j*2-i-1 < 0:
                schedule[i][2*size-j*2-i-1] = j + 1
            else:
                schedule[i][size-j*2-i-1] = j + 1

# parameters
teams = 10
matches = 5

# prepare the schedule, 0's designate free space  
schedule = [[0 for i in range(teams)] for j in range(teams)]

simpleNRooks(teams, matches, schedule)

print 'Final schedule'
for i in range(teams):
    print schedule[i]

If you want to get a different data structure out (for example a list of pairs by rounds) you can use the same principle, but change the loops.

I'm adding a separate answer given the new constraints, as I think it's clearer than adding to my old answer.

Split the 30 teams into 5 groups each of 6 teams: A B C D E
For the first period Group A and B play.
Then C&D, E&A, B&C, D&E, for the next 4 fifteen minute segments.

So at the end of 5 * 15 minutes: Every team has played twice, with at least one rest period between goes.

Have 20 periods and everyone has played 8 times.

It should be easy to allow a team in group B, for example, to play against 8 of the other teams from the 17 other teams in A,B & C groups.

For example play A teams against matching B teams, then later, B teams against matching C teams, then reverse lists, then within groups, then MOD 2, MOD 3 between groups, and within groups.

That just leaves minimising travel time, and ensuring that every team plays every game type. But solve that for one group, and you can apply the same solution to all the other ones?