问题描述
N支队伍进行比赛，要求：
- 任意两支队伍交且仅交过一次手
- 每天每支队伍至多打一场比赛
- 比赛尽快完成
问题等价于构造一个N×M矩阵，表示N支队伍比赛M天，第一列固定为1到N，表示每支队伍的编号，第i行表示第i支队伍每天的对手，-1表示没有对手不比赛。
第i行第j列的数字表示第i队在第j天跟a[i][j]打比赛，那么a[a[i][j]][j]=i必然成立。
先说结论
如果N为2的幂，则比赛日程为N×N的矩阵，也就是比赛在N天内完成，这是最完美的方法
如果N为偶数，则比赛日程也为N×N的矩阵
如果N为奇数，则比赛日程为N×(N)的矩阵
当N为2的幂
当N为2的幂，比赛日程为N阶方阵。
分治问题为N/2，得到一个N/2的方阵。相当于大方阵均分成四份，求出来左上角那一份来。把那一份进行一些平移变换复制到另外三份。
from pprint import pprint
def go(x):
if x == 2:
return [[0, 1], [1, 0]]
half = x // 2
a = go(half)
t = [[0] * x for _ in range(x)]
for i in range(half):
for j in range(half):
t[i][j] = a[i][j]
t[i + half][j] = a[i][j] + half
t[i][j + half] = a[i][j] + half
t[i + half][j + half] = a[i][j]
return t
N = 2 ** 3
ans = go(N)
pprint(ans)
当N不是2的幂
当N不是2的幂时，分类讨论：
- 当N为偶数，直接构造N阶方阵
- 当N为奇数，直接构造N+1阶的方阵，然后删掉最后一行
所以将一切情况都转化成了偶数阶方阵的构造。下面分类讨论偶数阶方阵的构造：
记half=N/2
- 当half为偶数时，直接计算half阶方阵，构成左上角，完成了1/4的任务，然后平移到另外三个位置
- 当half为奇数时，分两部分完成，左半部分和右半部分。左半部分为前half+1天的安排，右半部分为后half-1天的安排。
左上角相当于构造half+1阶（half+1必为偶数）的方阵，右上角相当于循环移位操作。
实际上，只要知道前half队的比赛，就知道了后half队的比赛
下面看一个11个队参加方阵的例子
[[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, -1],
[1, 0, 4, 2, 5, 3, 7, 6, 10, 8, -1, 9],
[2, 5, 0, 1, 3, 4, 8, -1, 6, 7, 9, 10],
[3, 4, 5, 0, 2, 1, 9, 10, -1, 6, 8, 7],
[4, 3, 1, 5, 0, 2, 10, 9, 7, -1, 6, 8],
[5, 2, 3, 4, 1, 0, -1, 8, 9, 10, 7, 6],
[6, 7, 8, 9, 10, -1, 0, 1, 2, 3, 4, 5],
[7, 6, 10, 8, -1, 9, 1, 0, 4, 2, 5, 3],
[8, -1, 6, 7, 9, 10, 2, 5, 0, 1, 3, 4],
[9, 10, -1, 6, 8, 7, 3, 4, 5, 0, 2, 1],
[10, 9, 7, -1, 6, 8, 4, 3, 1, 5, 0, 2]]
from pprint import pprint
def check(a):
# 检查答案是否正确
print('{}行{}列'.format(len(a), len(a[0])))
for i in range(0, len(a)):
for j in range(1, len(a[0])):
if a[i][j] != -1:
if i != a[a[i][j]][j]:
print("第{}天第{}人错误".format(j, a[i][j]))
return
print("完全正确")
def f(N): # N一定为偶数
if N == 2:
return [[0, 1], [1, 0]]
half = N // 2
a = go(half)
if half % 2 == 0:
t = [[-1] * N for _ in range(N)]
for i in range(half):
for j in range(half):
t[i][j] = a[i][j]
t[i + half][j] = a[i][j] + half
t[i][j + half] = a[i][j] + half
t[i + half][j + half] = a[i][j]
return t
else:
t = [[-1] * N for _ in range(N)]
for i in range(half):
for j in range(half + 1): # 对于前half+1项
t[i][j] = a[i][j]
t[i + half][j] = (a[i][j] + half) % N
t[i][half - i] = half + i
t[half + i][half - i] = i
for j in range(half + 1, N): # 对于后half-1项
t[i][j] = (i + j) % half + half
t[t[i][j]][j] = i
return t
def go(N):
if N % 2 == 0:
a = f(N)
return a
else:
a = f(N + 1) # 需要去除最下面一行和最左面一列
t = [[a[i][j] if a[i][j] != N else -1 for j in range(N + 1)] for i in range(N)]
return t
N = 5
ans = go(N)
check(ans)
pprint(ans)
参考资料
李健勇, 李晔, 刘艳红,等. 任意数量选手的循环赛赛程分治算法[J]. 郑州轻工业学院学报自然科学版, 2007, 22(4):122-125.