一尘不染

循环锦标赛的调度算法?

algorithm

我最近学习了一些东西,并与Donald Knuth见了面。但是我没有找到解决我问题的正确算法。

问题 我们有n名球员组成的联赛。他们每周都有一场比赛。在n-1周内,每个团队都在互相对抗。一天有n /
2场比赛。但一个团队每周只能战斗一次。如果我们生成一个(n / k)组合,我们将获得所有组合…(假设k = 2),但是我需要以正确的顺序进行组合。

我的第一个建议是……不是最好的建议。我只是做了一个阵列,然后让计算机尝试一下,如果他找到正确的方法。如果不是,请回到开始,重新整理数组,然后再做一次,好吧,我用PHP(n
= 8)对其进行了编程,结果是可行的,但是要花很多时间,而对于n = 16,它给了我超时也一样

所以我想,也许我们找到一种算法,或者任何人都知道一本书涵盖了这个问题。

这是我的代码:http :
//pastebin.com/Rfm4TquY


阅读 257

收藏
2020-07-28

共1个答案

一尘不染

经典算法的工作原理如下:

编号球队1..n。(在这里,我取n = 8。)

将所有团队写成两行。

1 2 3 4
8 7 6 5

列显示了该轮比赛中将参加比赛的球队(1对8、2对7,…)。

现在,保持1个固定,但轮换其他所有团队。在第二周,你得到

1 8 2 3
7 6 5 4

在第3周,

1 7 8 2
6 5 4 3

这种情况一直持续到第n-1周,在这种情况下,

1 3 4 5
2 8 7 6

如果n为奇数,则执行相同的操作,但添加一个虚拟团队。与假人队比赛的人在那周再见

2020-07-28