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

在国际象棋比赛中有一个非常简单的系统,叫做循环赛。

我们的想法是把运动员分到桌子的两边。其中一个玩家被指定为“中心”(因为缺乏更好的词汇)。比赛的开始是让运动员面对面地比赛。在第一轮比赛结束后,除了中心以外的所有人都向前移动一把椅子,白/黑(在运动项目中为主客场)顺序被切换。当选手们坐在原来的位置时,整个循环赛就结束了。如果你想让每个人都玩两次,那就再做一次。

Wikipedia article 包含实现细节。

在你的特殊情况下,我会尝试做一次循环赛,包括所有球队。然后你对每一个赛区都做同样的事情,为了确保每个赛区内的球队在主场和客场各打一次,从第一轮罗宾开始检查球队在那一轮的比赛方式。

当然,在比赛结束之前,你会打好所有的分区间比赛(因为最后一场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()

有两种算法,一种用于奇数组,一种用于偶数组,以确保循环发生。

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

奇数队

算法是顺时针旋转所有团队。如果我们有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 

从程序上讲,有几种方法可以实现这一点。也许上面发布的代码也会做同样的事情,哈哈。

我会把这些约束编码为布尔公式,并使用一些SAT求解器来获得解决方案(例如,McISAT为C++,SAT4J为Java,甚至可以编写自己的简单求解器)。这些解算器的输入由dimacs进行标准化。

也见 “社会高尔夫球手问题的SAT编码”和“比赛日程的基于SAT的调度程序”用于类似问题的SAT编码。

这是一个实现的例子

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方法所显示的。UDD。 希望这有帮助,尽管这不是一个完整的解决方案