我有一个循环赛，我为 8 个团队创建了所有必要的比赛(每个参与者 7 场比赛)。然而，我需要每个参与者进行 10 场比赛，这意味着我需要重复比赛，而且 1 场比赛和 5 场比赛不能互相比赛。您可以从下面的数据中看到我为每个参与者生成的游戏(游戏数量)按照创建顺序(即回合)生成。
我正在尝试找出复制比赛的最佳方法，并以这样一种方式最终分配比赛，即没有比赛重复三次，但每个参与者仍然保留 10 场比赛，并且有 1 场和 5 场比赛没有比赛彼此。任何建议都有助于解决这个问题。这也需要是其他可能性仍然有效的通用解决方案。
1 (6)
1 vs 2
1 vs 3
1 vs 4
1 vs 6
1 vs 7
1 vs 8
2 (7)
1 vs 2
2 vs 4
2 vs 3
2 vs 6
2 vs 5
2 vs 8
2 vs 7
3 (7)
3 vs 4
1 vs 3
2 vs 3
3 vs 7
3 vs 8
3 vs 5
3 vs 6
4 (7)
3 vs 4
2 vs 4
1 vs 4
4 vs 8
4 vs 7
4 vs 6
4 vs 5
5 (6)
5 vs 6
5 vs 7
5 vs 8
2 vs 5
3 vs 5
4 vs 5
6 (7)
5 vs 6
6 vs 8
6 vs 7
2 vs 6
1 vs 6
4 vs 6
3 vs 6
7 (7)
7 vs 8
5 vs 7
6 vs 7
3 vs 7
4 vs 7
1 vs 7
2 vs 7
8 (7)
7 vs 8
6 vs 8
5 vs 8
4 vs 8
3 vs 8
2 vs 8
1 vs 8
最佳答案
首先，您没有严格定义什么是“均匀分布”的匹配。所以我建议这意味着每对球队都打 1 或 2 场比赛。有了这个限制，我有一个针对您的原始案例的解决方案以及对一般案例的一些想法。
原始案例
8 支球队，每支球队必须打 10 场比赛，球队 1 不应与球队 5 比赛。这是匹配矩阵:
1 2 3 4 5 6 7 8
----------------------
1 | 0 2 2 1 0 1 2 2
2 | 2 0 1 2 1 2 1 1
3 | 2 1 0 2 2 1 1 1
4 | 1 2 2 0 2 1 1 1
5 | 0 1 2 2 0 2 2 1
6 | 1 2 1 1 2 0 1 2
7 | 2 1 1 1 2 1 0 2
8 | 2 1 1 1 1 2 2 0
以及根据值对单元格进行着色的相同矩阵:
这个矩阵是对称的，每行(和每列)总和为10，也就是说每支球队的比赛总数为10场。所有值都是 1 或 2，除了主对角线上的零(球队不与自己比赛)和 (1, 5) 和 (5, 1) 单元格上的零(球队 1 和 5 不互相比赛)。
一般情况
我将通过多个步骤解释我是如何为原始案例构建矩阵的。这些步骤可以针对几种不同的条件进行概括。但不适合所有人。我不建议针对大多数一般情况的解决方案。
- 从矩阵开始，所有可以参加比赛的球队都只参加一场比赛。此矩阵的行总和为
[6 7 7 7 6 7 7 7]，其中 6 代表位置 1 和 5。 - 尽量使每一行的总和相同。为此，在团队 1 和 8、1 和 7、5 和 4、5 和 3、2 和 6 之间添加游戏。总和现在是
[8 8 8 8 8 8 8 8]。不错。 - 尝试为每支球队增加两场比赛，其中禁止使用前一项比赛。在此步骤中，仅对前四支队伍执行此操作。添加团队 1 和 2、2 和 4、4 和 3、3 和 1 之间的游戏。总和现在是
[10 10 10 10 8 8 8 8]。 - 对最后四支队伍重复之前的模式。总和现在是
[10 10 10 10 10 10 10 10]。每对球队(允许比赛)进行 1 或 2 场比赛。我们完成了。
另一个想法，可能会有帮助。在均匀分布的比赛中，允许的对局之间的游戏次数可能相差不超过 1。我们可以这样想:所有对局都玩 N 局，几个对局玩 N +1 游戏。在我的解决方案中，我开始让所有对都玩 1 场比赛。它给出了初始总和，必须通过选择这几对玩另一场游戏来更正。因此，一般问题可以重新表述如下:如何将几个 1 放入零对称矩阵的允许位置，以便行的总和等于给定的向量？
关于algorithm - 平均重复游戏以达到每个参与者的最大数量，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/26704665/