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

Question

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

我被要求构建一个应用程序来管理体育联盟。 大多数概念都相当容易理解，除了这个：如何生成一个没有重叠的比赛时间表（球队一次对阵 2 支球队），其中一个分区中的一支球队与它的球队比赛两次，但与来自其他球队的球队比赛。其他部门一次，并确保时间表中没有漏洞（每个团队每周都进行比赛）

现在，该过程是使用我为实现此目的而构建的罗塞塔石碑类型电子表格手动完成的，但它仅适用于它设计的团队数量。 我为 30 个团队、24 个团队和 28 个团队制作了变体。 我不想不断地尝试重新调整我的翻译表，而是希望能够编纂该逻辑并调整该过程。

想法？

Answer 1

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

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

团队数量为奇数

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

在国际象棋锦标赛中使用了一个非常简单的系统，称为循环赛。

这个想法是将玩家分成桌子的两侧。 其中一名玩家被指定为“中心”（为了需要一个更好的词）。 比赛开始时，选手们面对面对战。 第一轮结束后，除了中心之外，每个人都向前移动一把椅子，并且白/黑（体育比赛中的主场/客场）顺序交换。 当选手们坐在原来的位置上时，整个循环赛就结束了。 如果你想让每个人都玩两次，只需再做一次同样的事情即可。

维基百科文章，其中包含实现详细信息。

在你的特殊情况下，我会尝试进行一次循环赛，包括所有团队。 然后，您对每个分区执行相同的操作一次，并确保分区内的球队在主场和客场互相比赛一次，从第一轮循环赛中检查球队在该轮中的比赛方式。

当然，这样做的缺点是，您将在锦标赛结束之前参加所有分区间比赛（因为最后 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 3

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

也可以看看
“A SAT Encoding for the Social Golfer Problem”和“A SAT Based Scheduler for Tournament Schedules”用于类似问题的 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 方法应该做的。
希望这会有所帮助，尽管它不是一个完整的解决方案

Answer 5

这是我在 Clojure 中的解决方案，实现了 Jas Panesar 的建议。

(defn rotate
  "Creates a new vector with the first element put at its end."
  [v]
  (if (or (empty? v) (= (count v) 1))
    v
    (let [head (first v)
          tail (rest v)]
      (flatten (vector tail head)))))

(defn pair-up
  "Pairs up each of the given teams against each other."
  ([teams]
   (let [anchor (first teams)
         remainder (rest teams)
         phases (count remainder)
         wheel (take phases (iterate rotate remainder))
         rotated-teams (map #(flatten (vector anchor %)) wheel)]
     (map #(partition 2 %) rotated-teams))))

以下是如何在 REPL 中使用它：

> (pair-up [:a :b :c :d])
(((:a :b) (:c :d)) ((:a :c) (:d :b)) ((:a :d) (:b :c)))

> (pair-up [:a :b :c :d :e :f])
(((:a :b) (:c :d) (:e :f))
 ((:a :c) (:d :e) (:f :b))
 ((:a :d) (:e :f) (:b :c))
 ((:a :e) (:f :b) (:c :d))
 ((:a :f) (:b :c) (:d :e)))