algorithm - Sorting pairs of teams with non-repeating | Round-robin tournament

Question

I'm generating schedule for the tournament. Each team should play exactly 8 games. Number of teams 2 < n < 36

For sorting teams into pairs I'm using Round Robin algorithm to get a table, example of 6 teams :

Then I convert it into the set of pairs:

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

The question is how to sort this set, in order to get schedule, where the same team can't play 2 games in a row. But if it's impossible, minimize the number of exceptions.

---

Example with new algorithm:

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 场比赛。我正在尝试提出一个公式，并将相应地更新这篇文章。