Round robin schedule

There are $n$ players to play a tennis round robin. Design a competition schedule that meets the following criteria:

• Each player must play $n − 1$ other players once each;

• Each player can only race once a day;

• When $n$ is even, the round robin is played for $n − 1$ days.

• When $n$ is odd, the round robin is played for $n$ days.

Analysis

When n is a power of two

When $n=2^k,k=1,2,3,4...$, it is easy. We can divide players into 2 parts. The schedule of $n＝2k$ players can be done by the schedule of $n/2＝2k-1$. Perform the split recursively until there are only two players left, and the schedule is simple: just let the two players play each other. Then the solution of the original problem can be obtained by gradually merging the solutions of the subproblems.

void tourna(int n) //基本的分治算法
{
    if(n==1){a[0][0]=1;return;}
    tourna(n/2); //分治
    copy(n); //合并
}

void copy(int n)
{
    int m=n/2;
    for(int i=0;i<m;i++)
    for(int j=0;j<m;j++){
        //由左上角小块的值算出对应的右上角小块的值
        a[i][j+m]=a[i][j]+m;
        //由右上角小块的值算出对应的左下角小块的值
        a[i+m][j]=a[i][j+m];
        //由左上角小块的值算出对应的右下角小块的值
        a[i+m][j+m]=a[i][j];
    }
}

tips: $a[i][j]$ means the rival that the $i$ th player meet in day $j$.

When n is not a power of two

Let’s talk about what happens when n is not a power of two.

We find that when n is odd, there must be one team empty every day. At this point we assume that there is another non-existent team playing against the empty team, unifying our model for the Odd-even case. The schedule for $n$ is similar to the schedule for even $n+1$.
For example, when $n=4$:

When $n=3$

To sum up, when n is odd, we can convert it to even.

Next we have the difficult problem of combining matrices.

When $n/2$ is even, it is like when $n=2^k$

When $n/2$ is odd, I referenced 猪一戒的博客

Let’s think about what happens when n is equal to 6.

We divide six people into two groups of three ([0,1,2],[3,4,5]), and then find that three is an odd number. Then we add one dummy in each group: X and Y; So you have four people in each group, and you divide those four people by two, and you get a small group of pairwise pairs.

Firstly, we see [0，1]; [2,x]

Combine these two:

Here, we want to get a match arrangement of 3 players, so we drop the imaginary X and replace its position with / :

Then we also follow this rule, schedule [3,4,5].

We have two 3x4 matrices (where the first column represents each team, which is really only three days), and we end up with a 6 by 6 matrix (where the first column represents each team, which is really only five days).

So let’s just merge the top two matrices.

The races for the first three days are almost finished, we just need to fill in the corresponding races in the slash /. Obviously, you could have two teams playing each other every day. (There are no slashes in the program, or imaginary teams, for easy monitoring)

In the matrix above, [0,1,2] and [3,4,5] have been compared within the group, and the group has been compared once, and the rest only need to rotate twice to get the match situation of the next two days.

So we can get the combination of two odd matrices.

In the program, our thinking is not strictly “merge”, but “extend”. For example, for “merging two 3x4 matrices”, we are “expanding one 3x4 matrix into a 6x6 matrix” (because the two 3x4 matrices have the same size and the same sorting order, so we only need to do it once).

Code

#include<stdio.h>
#include<stdlib.h>
#include"Check.cpp"

void copy(int n, int **a)//偶数情况
{
	//printf("当前行号%05d\n",__LINE__);
	int m=n/2;
	for(int i=0;i<m;i++){
		for(int j=0;j<m;j++){
			//由左上角小块的值算出对应的右上角小块的值
			a[i][j+m]=a[i][j]+m;
			//由右上角小块的值算出对应的左下角小块的值
			a[i+m][j]=a[i][j+m];
			//由左上角小块的值算出对应的右下角小块的值
			a[i+m][j+m]=a[i][j];
		}	
	}
}

void copyodd(int n, int **a) // n/2 为奇数时的合并算法
{
	printf("当前行号%05d\n",__LINE__);
	int m=n/2;
	int b[m];
	for(int i=0;i<m;i++){
		b[i]=m+i;
		b[m+i]=b[i];
	}
	for(int i=0;i<m;i++){
		//由左上角小块的值算出相应的左下角小块的值
		for(int j=0;j<m+1;j++){
			if(a[i][j]>=m){
				a[i][j]=b[i];
				a[m+i][j]=(b[i]+m)%n;
			}	else a[m+i][j]=a[i][j]+m;
		}
		//由左上角小块的值算出相应的右上角和右下角小块的值
		for(int j=1;j<m;j++){
			a[i][m+j]=b[i+j];
			a[b[i+j]][m+j]=i;
		}
	}
}



void merge(int n, int **a) //合并算法
{
	if((n/2)>1 && (n/2)%2 == 1) copyodd(n,a); //n/2 为奇数时,注意是 (n/2)%2 == 1，n别忘了/2 
	else copy(n,a);
}


void tournament(int n, int **a) //循环赛算法
{
	printf("当前行号%05d\n",__LINE__);
	if(n==1){a[0][0]=0;return;}
	if(n%2 == 1)	{tournament(n+1,a);return;} //n为奇数，分治
	tournament(n/2,a); //n为偶数，分治
	merge(n,a); //合并
}


main()
{
	int n;
	scanf("%d",&n);
	
	//创建数组
	int **a;
	a = (int**)malloc(sizeof(int*)*n);
	
	if(n%2==1){
		for(int i=0; i<n+1; i++)	a[i] = (int*)malloc(sizeof(int)*(n+1));
	} else {
		for(int i=0; i<n; i++)	a[i] = (int*)malloc(sizeof(int)*n);
	}
	
	//生成循坏赛矩阵
	tournament(n,a);
	
	//打印
	printf("当前行号:%05d\n",__LINE__);
	for(int i=0; i<n; i++){
		for(int j=1; j<(n%2 == 1 ? n+1 : n); j++){
			if(a[i][j]<n)	printf("%d ",a[i][j]);
			else printf("x ");
		}
		printf("\n");
	}
	
	//检验程序
	if(Check(a,n)==1) printf("This gametable is availuable.\n");
	else printf("This gametable is unavailuable.\n");
	if(n%2 ==1){
		for(int i=0; i<n; i++)	free(a[i]);
	} else {
		for(int i=0; i<n+1; i++)	free(a[i]);
	}
	free(a);
}

Test

The test program checks the matrix we generated. There are two ways to do it.

• Each team will play a match against the other teams

• Each team will play only one match per day

The test program code is as follows.

int Check(int **a, int n)
{
	int column;
	if(n%2==1) column=n+1;
	else column=n;
	int flag=0;
	int check=1;//check为0说明不符合条件，停止检验。 
	//检验每个队伍都与其他队伍比赛 
	for(int i=0; i<n&&check==1; i++){
		for(int k=0; k<n&&check==1; k++){
			flag=0;
			for(int j=0;j<column&&flag==0;j++){
				if(a[i][j] == k) flag=1;
			}
			if(flag==0) check=0;
		}
	}
	//检验某天是否有队伍重复比赛
	int times[n];
	for(int j=1; j<column&&check==1; j++){
		for(int w=0; w<n; w++) times[w]=0;
		for(int i=0; i<n&&check==1; i++){
			times[a[i][j]]++;
			if(times[a[i][j]]>=2) check==0;
		}
	} 
	if(check==1) return 1;
	else return 0;
}

Result

• When $n=6$

• When $n=9$

They are all correct.