Parijat@SUN: Work hard but think smart

Problem Definition:
We need to schedule a fair-schedule for a football tournament played in a round robin league. A fair schedule means every team should have a match after same interval. If we have n teams there will be total of n(n-1)/2 matches. Each team should play a match after a guaranteed interval. Assuming n an even number, we can divide all the n(n-1)/2 matches in (n-1) clusters, each having eaxctly n/2 matches. In these clusters, each team should play exactly one match.Hence at the end of each cluster the total number of matches played by any team will remain the same. For example we have four teams, A, B, C, and D.
There will be 6 matches and 3 clusters and each cluster has 2 matches.
A possible clustering:

A vs B    A vs D     A vs C
C vs D    B vs C     B vs D

See that at the end of each cluster each team has played exactly same number of matches. Hence this is a fair schedule.

However note that this has a problem that team A can play the first match of cluster 1 and then can play the last match in cluster 2. If the number of matches in each cluster is 4, there will be 6 other team matches between the two matches of team A. Again team A could have the last match of cluster 1 and then first match of cluster 2 hence playing two consecutive mathces. Ensuring same number of intervals between all team's matches is the best solution but a costly one two. A suboptimal solution but a very effective one is the scenario described in the beginning.

The algorithm to solve this case should have a nXn table each cell initialized with 0.
As we schedule a match between team[i] and team[j], we replace 0 with scheduled day.

For each of the (n-1) cluster we start with a boolean array of size n, set all to true, indicationg team[i] is available for selection.
As we select a team for scheduling we set available[i] = false;

int teamCount;
int cluster = teamCount -1;
int[][] schedule;

initialize schedule to have 0 in all cells;

for each cluster do  {
            for all team do
                available[j] = true;
            for 1 to teamCount/2 {
                int nextRandom;
                do {
                    nextRandom = randomly select any available team;
                } while (!available[nextRandom]);
                int team1 = nextRandom;
                available[team1]=false;
                do {
                    nextRandom = randomly select any available team;
                } while ((schedule[team1][nextRandom] != 0) && (schedule[nextRandom][team1] != 0) || !available[nextRandom]);
                int team2 = nextRandom;
                available[team2]=false;
               
                if (schedule[team1][team2] == 0) {
                    schedule[team1][team2] = day;                   
                } else if (schedule[team2][team1] == 0) {
                    schedule[team2][team1] = day;                   
                }
                day = nextDay;
            }
}

int randomlySelectOnlyUnselected (boolean[] available) {

        int[] indexArray = new int[available.length];
        int count =-1;
        for (int i=0; i < available.length; i++) {
            if (available[i])
                indexArray[++count] = i;
        }
        if (count == -1 ) return -1;
        if (count == 0) return indexArray[0];

        Random R = new Random();
        int nextRandom = R.nextInt(count+1);
        return indexArray[nextRandom];
    }

Analyzing the time complexity:

The first of the do-while has a complexity of O(n). The secong do-while can explore almost all cells in schedule based on a fair random number generator
should be O(n²).
The outer-most for loop runs n-1 time and the inner for loop runs n/2 times.
Hence an expected time complexity O(n*(n/2)*(n+n²)) = O(n³)

Remember that the search space is all possible permuation (ordering) of all the matches being [n(n-1)/2]! and we know  [Stirling's approximation].

Problem Size	Time (ms)
10	15
12	32
16	47
20	78
24	94

  

 

Let's find a more efficient algorithm than this. Also need to discuss the additional steps required when n is an odd number.