CODEWITHSUNDEEP
algorithmmatchsports-league-scheduling-problem
Abdalla
Abdalla

Reputation: 2073

Match schedule algorithm, each team play specific number of matches

I have a specific number of teams. I want every team to play exactly 4 matches with 4 different opponents at 4 specified times.

The complication arises from that no team can play 2 different matches at the same time. For example if team 1 is playing like this

team1 vs team2, team1 vs team3, team1 vs team4, team1 vs team5

then team2 already has the first time slot occupied so team2 can play like this

(team2 vs team1), team2 vs team3, team2 vs team4, team2 vs team5

But here the problem arises, team3 will play in the second time slot with team1 and team2 and this can not be done.

I do not know what this algorithm can be called, but I am searching for algorithm to implement this.

I made a search to find round-robin and other tournament like matching algorithm and also the marriage problem, but I think my problem is different. Please correct me if I am wrong.

Any help is greatly appreciated.

Upvotes: 3

Views: 10902

Answers (3)

Django
Django

Reputation: 103

This algorithm will work for any number of teams.
Suppose there are 6 teams in a tournament.
enter image description here

This solution basically tells you how to fill the 6x6 matrix, and each entry in the matrix is the match between the teams in the row vs column.
Consider few rules in the algorithm
1. Increment value in the matrix from left to right and top to bottom. mat[0][0] = 1
2. Whenever i == j, then fill the matrix at [n-1][j] instead at [i][j]. Basically, no entry will be there at i==j
3. And whenever entry in the matrix reaches to 6, make it 1

We will follow this rule and start filling the matrix from [0][0] column-wise. Means first we will fill every row of 0th column then move to 1st column and so.
- At [0][0], apply rule 2. So fill mat[n-1][0] = 0
- At mat[1][0], fill next number ie 2 and similarly for [2][0], [3][0], [4][0]
- And now column 1, starts with value 2
- mat[1][0] = 2;
- At mat[1][1] apply rule 2, fill last row of current column ie mat[n-1][1] = 3

If you want that every team should play only one game with other team, use lower triangle.
And if you want that every team should play 2 games with other teams, one home and away use both lower and upper triangle.

Hope you guys understand my solution.
Cheers

Upvotes: 3

cohoz
cohoz

Reputation: 760

A simple algorithm:

Round 1
1  2  3  4
8  7  6  5

Then rotate places 2-8...

Round 2
1  8  2  3
7  6  5  4

Round 3
1  7  8  2
6  5  4  3

http://en.wikipedia.org/wiki/Round-robin_tournament#Scheduling_algorithm

(If there is an odd number, one can extend the this by adding a dummy pairing to indicate a bye, but then as Patricia Shanahan notes, not every team would play every round. So an even number of teams and at least six teams are needed to fit the requirements.)

Upvotes: 3

Patricia Shanahan
Patricia Shanahan

Reputation: 26185

I have concluded there is no solution if the number of teams is odd. Let N be the number of teams. We need a total of N*4/2 matches, four matches per team but each match counts for two teams. To do N*2 matches in four time slots we must average N/2 matches per slot. We can do at most floor(N/2) matches at a time. If N is odd, floor(N/2) < N/2.

Would a solution that only works for even N, if it exists, be useful?

Upvotes: 4

Related Questions