调度算法的循环赛？ [英] Scheduling algorithm for a round-robin tournament?

问题描述

我最近做学习的东西，满足了高德纳。但我没有找到合适的算法，我的问题。

I recently did studying stuff and meet up with Donald Knuth. But i didn't found the right algorithm to my problem.

问题我们必须有n个球员联赛。每星期他们有一个其他的比赛。在正1周每一个团队相互对抗。有n天/ 2场比赛。但一队只能打一次，在一个星期。如果我们产生一个（N / K）的组合，我们得到的所有组合...（假设K = 2），但我需要把他们在正确的顺序。

The Problem We have a league with n players. every week they have a match with one other. in n-1 weeks every team fought against each other. there are n/2 matches a day. but one team can only fight once in a week. if we generate an (n/k) combination we get all of the combinations... (assuming k = 2) but i need to bring them in the right order.

我的第一个建议是......不是最好的。我只是做了数组，然后让他找到了正确的方式在电脑尝试。如果没有，回去一开始，洗牌数组，并做一遍，好，我编写了它在PHP（N = 8），什么出来的作品，但需要很多的时间，而对于N = 16它给了我一个超时为好。

My first suggestion was... not the best one. i just made an array, and then let the computer try if he finds the right way. if not, go back to the start, shuffle the array and do it again, well, i programmed it in PHP (n=8) and what comes out works, but take many time, and for n=16 it gives me a timeout as well.

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

So i thought if maybe we find an algorithm, or anybody knows a book which covers this problem.

这是我的code： http://pastebin.com/Rfm4TquY

And here's my code: http://pastebin.com/Rfm4TquY

推荐答案

经典的算法是这样的：

数球队1..N。 （这里我取n = 8）。

Number the teams 1..n. (Here I'll take n=8.)

写的所有球队在两行。

1 2 3 4
8 7 6 5

该列显示哪些球队将在这一轮发挥（1比8,2比7，...）。

The columns show which teams will play in that round (1 vs 8, 2 vs 7, ...).

现在，保持1个固定，但旋转所有其他球队。第2周，您将获得

Now, keep 1 fixed, but rotate all the other teams. In week 2, you get

1 8 2 3
7 6 5 4

和3周，你会得到

1 7 8 2
6 5 4 3

此继续通过周n-1个，在这种情况下，

This continues through week n-1, in this case,

1 3 4 5
2 8 7 6

如果n为奇数，做同样的事情，但添加一个虚拟团队。无论是谁匹配的虚拟团队得到了再见的那个星期。

If n is odd, do the same thing but add a dummy team. Whoever is matched against the dummy team gets a bye that week.

这篇关于调度算法的循环赛？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！