CODEWITHSUNDEEP
algorithmsortingsports-league-scheduling-problem
Dmitrijs Bambulaks
Dmitrijs Bambulaks

Reputation: 47

Sorting pairs of teams with non-repeating | Round-robin tournament

I'm generating schedule for the tournament. Each team should play exactly 8 games. Number of teams 2 < n < 36

For sorting teams into pairs I'm using Round Robin algorithm to get a table, example of 6 teams :

Then I convert it into the set of pairs: 

1   4
2   3
3   2
4   1
5   6
6   5
1   2
2   1
3   5
4   6
5   3
6   4
...

The question is how to sort this set, in order to get schedule, where the same team can't play 2 games in a row. But if it's impossible, minimize the number of exceptions.

Example with new algorithm:

Upvotes: 3

Views: 4544

Answers (1)

Debosmit Ray
Debosmit Ray

Reputation: 5403

I will try to start an approach to answer this question. If asked, I can leave it as a community wiki, so that people can make edits to improve this answer.

Wikipedia Round-robin Tournament Scheduling Algorithm

Let's start with the case of 8 teams. [T1, T2, T3, T4, T5, T6, T7, T8]

Let us try to look at this problem like so..

T1 T2 T3 T4
T5 T6 T7 T8

So, now. Matches -> [(1,5), (2,6), (3,7), (4,8)].

Rotate the list clock-wise, but keep position of T1 fixed.

T1 T5 T2 T3
T6 T7 T8 T4

So, now. Matches -> [(1,5), (2,6), (3,7), (4,8), (1,6), (5,7), (2,8), (3,4)].

In this case, there will be 7 possible rotations before duplication start to occur. In a traditional round-robin tournament, there are (n/2)*(n-1) games, where n is the number of teams. This should work regardless of the number of teams involved. [If you encounter n%2 == 1, put an X to make the set even and continue as normal; one team will sit out on one match].

If you need to ensure that each team must play 8 games, make exactly 8 rotations when the number of teams is even.

This method correspondingly ensure, that given a sufficient number of teams, same teams won't play back to back games.

Edit.

Let's start with the case of 3 teams. [T1, T2, T3]

Let us try to look at this problem like so..

T1 T2
T3 X

So, now. Matches -> [(1,3), (2,X)].

Rotate the list clock-wise, but keep position of T1 fixed.

T1 T3
X   T2

So, now. Matches -> [(1,3), (2,X), (1,X), (3,2)].

Next case, Matches -> [(1,3), (2,X), (1,X), (3,2), (1,2), (X,3)].

Next case, Matches -> [(1,3), (2,X), (1,X), (3,2), (1,2), (X,3), (1,3), (2,X)].

....

Matches -> [(1,3), (2,X), (1,X), (3,2), (1,2), (X,3), (1,3), (2,X), (1,X), (3,2), (1,2), (X,3), (1,3), (2,X), (1,X), (3,2), (1,2), (X,3), (1,3), (2,X), (1,X), (3,2), (1,2), (X,3), (1,3), (2,X), (1,X), (3,2), (1,2), (X,3)].

1 -> [3,X,2,3,X,2,3,X,2,3,X,2]
2 -> [X,3,1,X,3,1,X,3,1,X,3,1]
3 -> [1,2,X,1,2,X,1,2,X,1,2,X]

If you notice the pattern, you will see that under these conditions, it is impossible to ensure that teams don't play back-to-back games. It required 12 rotations to get each team to have played 8 games. I am trying to come up with a formula and will update this post accordingly.

Upvotes: 2

Related Questions