我最近学习了一些东西,并与Donald Knuth见了面。但是我没有找到解决我问题的正确算法。
问题 我们有n名球员组成的联赛。他们每周都有一场比赛。在n-1周内,每个团队都在互相对抗。一天有n / 2场比赛。但一个团队每周只能战斗一次。如果我们生成一个(n / k)组合,我们将获得所有组合…(假设k = 2),但是我需要以正确的顺序进行组合。
我的第一个建议是……不是最好的建议。我只是做了一个阵列,然后让计算机尝试一下,如果他找到正确的方法。如果不是,请回到开始,重新整理数组,然后再做一次,好吧,我用PHP(n = 8)对其进行了编程,结果是可行的,但是要花很多时间,而对于n = 16,它给了我超时也一样
所以我想,也许我们找到一种算法,或者任何人都知道一本书涵盖了这个问题。
这是我的代码:http : //pastebin.com/Rfm4TquY
经典算法的工作原理如下:
编号球队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为奇数,则执行相同的操作,但添加一个虚拟团队。与假人队比赛的人在那周再见。