algorithm - 对具有非重复 | 的团队进行排序循环赛

Question

我正在为锦标赛生成时间表。每支球队应该正好打 8 场比赛。队伍数量 2 < n < 36

为了将团队分成两对，我使用 Round Robin 算法得到一个表格，例如 6 个团队:

然后我把它转换成对的集合:

1   4
2   3
3   2
4   1
5   6
6   5
1   2
2   1
3   5
4   6
5   3
6   4
...

问题是如何对这组比赛进行排序，以便获得赛程表，同一支球队不能连续打 2 场比赛。但如果不可能，请尽量减少异常的数量。

---

新算法示例:

Answer 1

我将尝试开始一种方法来回答这个问题。如果被问到，我可以将其保留为社区 wiki，以便人们可以进行编辑以改进此答案。

Wikipedia Round-robin Tournament Scheduling Algorithm

让我们从 8 个团队的案例开始。[T₁, T₂, T₃, T₄, T₅ , T₆, T₇, T₈]

让我们试着这样看待这个问题..

T₁ T₂ T₃ T₄
T₅ T₆ T₇ T₈

所以，现在。匹配 -> [(1,5), (2,6), (3,7), (4,8)].

顺时针旋转列表，但保持 T₁ 的位置固定。

T₁ T₅ T₂ T₃
T₆ T₇ T₈ T₄

所以，现在。匹配 -> [(1,5), (2,6), (3,7), (4,8), (1,6), (5,7), (2, 8), (3,4)].

在这种情况下，在开始复制之前将有 7 次可能的旋转。在传统的循环赛中，有 (n/2)*(n-1) 场比赛，其中 n 是球队的数量。无论涉及多少团队，这都应该有效。 [如果遇到n%2 == 1，放一个X使集合均匀，然后照常继续；一支球队将缺席一场比赛]。

如果需要保证每支球队必须打8场比赛，当球队数量为偶数时，正好8轮。

这种方法相应地确保，如果有足够数量的球队，相同的球队不会背靠背比赛。

编辑。

让我们从 3 个团队的案例开始。[T₁, T₂, T₃]

让我们试着这样看待这个问题..

T₁ T₂
T₃ X

所以，现在。匹配 -> [(1,3), (2,X)].

顺时针旋转列表，但保持 T₁ 的位置固定。

T₁ T₃
X T₂

所以，现在。匹配 -> [(1,3), (2,X), (1,X), (3,2)].

下一个案例，匹配 -> [(1,3), (2,X), (1,X), (3,2), (1,2), (X, 3)].

下一个案例，匹配 -> [(1,3), (2,X), (1,X), (3,2), (1,2), (X,3), (1,3), (2,X)].

....

匹配 -> [(1,3), (2,X), (1,X), (3,2), (1,2), (X,3), (1,3), (2,X), (1,X), (3,2), (1,2), (X,3), (1,3 ), (2,X), (1,X), (3,2), (1,2), (X,3), (1,3), (2,X) , (1,X), (3,2), (1,2), (X,3), (1,3), (2,X), (1,X), (3,2), (1,2), (X,3)].

1 -> [3,X,2,3,X,2,3,X,2,3 ,X,2]
2 -> [X,3,1,X,3,1,X,3,1,X,3, 1]
3 -> [1,2,X,1,2,X,1,2,X,1,2, X]

如果您注意到这种模式，就会发现在这种情况下，不可能确保球队不进行背靠背比赛。需要轮换 12 次才能让每支球队打完 8 场比赛。我正在尝试想出一个公式，并将相应地更新这篇文章。