如何自动生成体育联盟赛程

Question

我首先要说的是，我明白这个话题很复杂，可能没有一个简单的答案。如果它很容易那么每个人都会这样做。那就是说......

我被要求建立一个管理体育联盟的应用程序。除了这一点之外，大多数概念都很容易理解：如何在没有重叠的情况下制定比赛时间表（球队同时参加2支球队），其中一支球队的球队两次参赛，但是参加球队的比赛。其他部门一次，并确保计划中没有漏洞（每个团队每周播放）

现在，该过程是使用我为此目的而构建的rosetta stone类型电子表格手动完成的，但它仅适用于其设计的团队数量。我为30个团队，24个团队和28个团队做了变化。我不想继续尝试重新调整我的翻译表，而是希望能够编写该逻辑并调整该过程。

思想？

Answer 1

有一个非常简单的系统用于例如国际象棋比赛称为循环赛。

这个想法是将球员分成桌子的两边。其中一个玩家被指定为<！>“hub <！>”; （想要一个更好的词）。比赛开始时让球员彼此面对面对战。在第一轮之后，除轮毂之外的所有人都向前移动一把椅子，并且切换白/黑（运动中的主场/客场）顺序。当玩家坐在他们原来的地方时，整个循环比赛就结束了。如果你想让每个人都玩两次，那就再做一次。

维基百科文章，其中包含实施细节。

在你的特殊情况下，我会尝试一次包括所有球队的循环赛。然后你为每个分区做一次同样的事情，并确保分区内的队员在主场和对方之间互相比赛一次，从第一轮开始检查球队在那一轮比赛中的表现。

当然，这方面的缺点是你将在锦标赛结束前很好地进行所有的分区比赛（因为最后的n-1场比赛是针对分区内的球队[n =分区球队的数量] ]）。如果这是一个问题，你可以简单地交换一下匹配。

我实际上写了一个简单的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()

Answer 2

有两种算法，一种用于奇数队，一种用于偶数队，以确保循环赛发生。

如果可以的话，我会为你生成一个图形。

ODD＃of 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   

此时我们已经完成了一次循环赛，每个人都互相比赛一次......下一轮将再次出现......

1 2
3 4
5

甚至是团队

当我们拥有偶数队伍时，你会做同样的轮换，除非你将队伍＃1固定在固定位置，并以顺时针方式将所有其他队伍围绕＃1旋转。所以，如果我们有4个团队..

1 2 --> 1 3 --> 1 4 
3 4     4 2     2 3 

这将是一个完整的循环赛...下一场比赛将是..

1 2 
3 4 

以编程方式，有几种方法可以解决这个问题。也许上面发布的代码做同样的事情大声笑..

Answer 3

我只是将这些约束编码为布尔公式并使用一些SAT求解器来获得解决方案（例如，用于C ++的MiniSAT，用于Java的SAT4J，甚至可以编写自己的简单求解器）。这些求解器的输入由DIMACS标准化。

另见 <！>;针对社交高尔夫球手问题的SAT编码<！>和<！>“基于SAT的锦标赛时间表安排程序<！>”;对于类似问题的SAT编码。

Answer 4

这是一个实现的镜头

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 :)

我只是在纸上测试过，但是我的设置确实有效。通过在团队列表开始和列表结束之间交替，我避免了在我的论文测试中同一团队必须一遍又一遍地（或在同一天重复播放）的情况将每个可能的遭遇表示为不同的对偶，但这基本上就是CanPlay方法应该做的事情。 希望这会有所帮助，尽管它不是一个完整的解决方案