.net 如何自动生成体育联赛时间表
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/1037057/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How to automatically generate a sports league schedule
提问by thaBadDawg
I'll start of by saying that I understand that this topic is complicated and that there probably isn't an easy answer. If it were easy then everybody would be doing it. That being said...
我首先要说的是，我知道这个话题很复杂，而且可能没有简单的答案。如果这很容易，那么每个人都会这样做。话虽如此...
I've been asked to build an application to manage a sports league. Most of the concepts are fairly easy to understand except for this one: How to generate a schedule of play where there are no overlaps (team plays 2 teams at once), where a team in a division plays its teams twice but plays teams from the other divisions once, and makes sure that there are no holes in the schedule (each team plays every week)
我被要求构建一个应用程序来管理一个体育联盟。大多数概念都相当容易理解，除了这个：如何在没有重叠的情况下生成比赛时间表（团队一次玩 2 支球队），其中一个部门的一支球队对阵自己的球队两次，但与来自其他球队的球队交手其他部门一次，并确保日程安排没有漏洞（每个团队每周都有比赛）
Right now the process is done manually using a rosetta stone type spreadsheet that I've built to serve this purpose, but it only works for the number of teams it was designed for. I have variations made for 30 teams, 24 teams and 28 teams. Rather than continually attempt to readjust my translation table, I'd like to be able to codify that logic and tweak that process instead.
现在，该过程是使用我为实现此目的而构建的 rosetta Stone 类型电子表格手动完成的，但它仅适用于它设计的团队数量。我为 30 支球队、24 支球队和 28 支球队制作了变化。与其不断尝试重新调整我的翻译表，我更希望能够编纂该逻辑并调整该过程。
Thoughts?
想法？
回答by Makis
There is a pretty straightforward system used in e.g. chess tournaments called round-robin.
在国际象棋比赛中使用了一个非常简单的系统，称为循环。
The idea is to divide the players to the two sides of a table. One of the players is designated as a "hub" (for a want of a better word). The tournament starts by having players facing each other playing against each other. After the first round everyone but the hub move one chair forward and the white/black (home/away in sports) order is switched. The entire round-robin competition is finished when the players sit in their original places. If you want everyone to play everyone twice just do the same again.
这个想法是将玩家分成桌子的两侧。其中一名玩家被指定为“枢纽”（因为想要一个更好的词）。比赛开始时让玩家面对面互相比赛。第一轮结束后，除轮毂外的所有人向前移动一把椅子，白/黑（运动中的主场/客场）顺序被转换。当球员坐在原来的地方时，整个循环赛都结束了。如果你想让每个人都玩两次，就再重复一遍。
Wikipedia articlewith implementation details.
包含实现细节的维基百科文章。
In your special case I would try doing the round robin once including all teams. Then you do the same for each division once and to make sure teams within divisions play each other once at home and once away, check from the first round robin what way the teams played in that round.
在您的特殊情况下，我会尝试进行一次循环赛，包括所有球队。然后你对每个分区做一次同样的事情，并确保分区内的球队在主场和客场比赛一次，从第一轮循环赛中检查球队在该轮比赛中的比赛方式。
The down-side of this is, of course, that you will play all inter-division matches well before the tournament finishes (since the last n-1 matches are against intra-division teams [n=number of teams in division]). If this is a problem you could simply swap matches around a bit.
当然，这样做的缺点是，您将在锦标赛结束前参加所有跨分区的比赛（因为最近的 n-1 场比赛是针对分区内的球队 [n = 分区中的球队数量]）。如果这是一个问题，您可以简单地交换一下匹配。
I actually wrote a simple Python script that does this. It didn't take many lines of code and produced pretty good results. This will create a schedule where each team plays each team in their division twice and once against teams in other divisions. There is no check to make sure that the teams meet each other twice in such a way that the same team is at home, however. But this code should give a good idea on how to create your own scheduling code.
我实际上编写了一个简单的 Python 脚本来执行此操作。它不需要很多代码行，并产生了相当不错的结果。这将创建一个时间表，其中每支球队都会在自己的分区中对每个团队进行两次比赛，并与其他分区的球队进行一次比赛。然而，没有任何检查可以确保两支球队在同一支球队在主场相遇两次。但是这段代码应该可以很好地说明如何创建自己的调度代码。
#!/usr/bin/python
div1 = ["Lions", "Tigers", "Jaguars", "Cougars"]
div2 = ["Whales", "Sharks", "Piranhas", "Alligators"]
div3 = ["Cubs", "Kittens", "Puppies", "Calfs"]
def create_schedule(list):
""" Create a schedule for the teams in the list and return it"""
s = []
if len(list) % 2 == 1: list = list + ["BYE"]
for i in range(len(list)-1):
mid = int(len(list) / 2)
l1 = list[:mid]
l2 = list[mid:]
l2.reverse()
# Switch sides after each round
if(i % 2 == 1):
s = s + [ zip(l1, l2) ]
else:
s = s + [ zip(l2, l1) ]
list.insert(1, list.pop())
return s
def main():
for round in create_schedule(div1):
for match in round:
print match[0] + " - " + match[1]
print
for round in create_schedule(div2):
for match in round:
print match[0] + " - " + match[1]
print
for round in create_schedule(div3):
for match in round:
print match[0] + " - " + match[1]
print
for round in create_schedule(div1+div2+div3):
for match in round:
print match[0] + " - " + match[1]
print
if __name__ == "__main__":
main()
回答by Jas Panesar
There are two algorithms, one for odd teams, one for even teams to make sure the round robin happens.
有两种算法，一种用于奇数队，一种用于偶数队以确保循环赛发生。
I am going to generate you a graphic if i can.
如果可以的话，我将为您生成一个图形。
ODD # of teams
奇数团队数
The algorithm is to rotate all the teams clockwise. If we had 5 teams:
算法是顺时针旋转所有团队。如果我们有 5 个团队：
1 2 --> 3 1 --> 5 3 --> 4 5 --> 2 4
3 4 5 2 4 1 2 3 1 5
5 4 2 1 3
At this point we have completed one round robin where everyone plays each other once... the next round would again be..
在这一点上，我们已经完成了一个循环赛，每个人互相比赛一次......下一轮将再次......
1 2
3 4
5
EVEN # of teams
偶数个团队
When we have an even number of teams, you do the same rotation, except you hold team #1 in fixed position and rotate all the other teams around #1 in a clockwise fashion. So, if we had 4 teams..
当我们有偶数个团队时，您进行相同的轮换，除了您将#1 团队固定在固定位置并以顺时针方式围绕#1 旋转所有其他团队。所以，如果我们有 4 个团队..
1 2 --> 1 3 --> 1 4
3 4 4 2 2 3
This would be one complete round robin... the next match up would be..
这将是一个完整的循环赛……下一场比赛将是……
1 2
3 4
Programmatically, There's a few ways you could approach this. Maybe the code posted above does the same thing lol..
以编程方式，有几种方法可以解决这个问题。也许上面发布的代码做了同样的事情，哈哈..
回答by MadH
I would just encode these constraints as a boolean formula and use some SAT-solver to obtain solutions (e.g. MiniSAT for C++, SAT4J for Java, and you could even write you own simple solver). The input to these solvers is standartized by DIMACS.
我只是将这些约束编码为一个布尔公式，并使用一些 SAT 求解器来获得解决方案（例如，用于 C++ 的 MiniSAT，用于 Java 的 SAT4J，您甚至可以编写自己的简单求解器）。这些求解器的输入由 DIMACS 标准化。
See also "A SAT Encoding for the Social Golfer Problem" and "A SAT Based Scheduler for Tournament Schedules" for SAT-encodings of similar problems.
另请参阅“A SAT Encoding for the Social Golfer Problem”和“A SAT Based Scheduler for Tournament Schedules”了解类似问题的 SAT 编码。
回答by Rune FS
here's a shot at an implementation
这是一个实现的镜头
public interface ITeam
{
bool PlaysOn(DateTime date);
bool canPlay(ITeam); //returns true if a game between the teams is legal (played once/twice
//already, same different divisions and other applicable rules
}
IEnumerable<ITeam> teams = null; //replace with initialization
IEnumerable<ITeams> reversed = team.Reverse();
IEnumerable<DateTIme> gameDays = null;//replace with initialization
var count = teams.Count();
foreach(var date in gameDays)
{
for(int i = 0;i<count;i++)
{
var innerTeams = i % 2 == 0 ? teams : reversed;
var team = (from t in innerTeams
where !t.PlaysOn(date)
select t).First();
var opp = (from t in teams
where !t.PlaysOn(date) && t.CanPlay(team)
select t).First();
SetupGame(team,opp);
}
} //lot of optimazation possible :)
I've only tested it on paper but for my setup it works. By alternating between starting at the start of the teams list and the end of the list I avoid the situations where the same team would have to play the same team over and over again (or repeatedly play on the same day) in my paper test I represented every possible encounter as a different opponnent but that's basically what the CanPlay method should do. Hope this helps, eventhough it not a complete solution
我只在纸上测试过它，但对于我的设置它有效。通过在团队列表的开头和列表的结尾之间交替开始，我避免了在我的纸笔测试中同一团队必须一遍又一遍地与同一团队比赛（或在同一天重复比赛）的情况将每一次可能的遭遇都表示为不同的对手，但这基本上是 CanPlay 方法应该做的。希望这会有所帮助，尽管它不是一个完整的解决方案
