algorithmsortingsports-league-scheduling-problem

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:

Solution

  • 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.