均匀复制游戏，以达到每个参与者的最大数量
我有一个循环锦标赛，在那里我为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
Stack Overflow用户
发布于 2014-11-03 16:00:31
首先，你没有严格定义什么是“均匀分布”的比赛。所以我建议这意味着每一对球队打一到两场比赛。有了这个限制，我对您的原始情况有了一个解决方案，并对一般情况有了一些想法。
原始案例
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之间的游戏。Sum现在是
[8 8 8 8 8 8 8 8]。很好。 - 尝试为每个团队添加两场比赛，其中前一项的配对是被禁止的。在此步骤中，仅对前四个团队执行此操作。在团队1和2，2和4，4和3，3和1之间添加游戏。Sum现在是最后四个团队的
[10 10 10 10 8 8 8 8]. - Repeat以前的模式。Sum现在是
[10 10 10 10 10 10 10 10]。每一对球队(允许比赛)玩1到2场比赛。我们完事了。
另一个想法，这可能会有帮助。在均匀分布的比赛中，允许的对之间的游戏数量可能相差不超过1。我们可以这样认为:所有对都玩N游戏，几对玩N+1游戏。在我的解决方案中，我从所有的配对开始玩一场游戏。它给出了初始和，必须通过选择这几对玩一个额外的游戏来修正。因此，一般的问题可能会被重新表述为:如何将多个1放入零对称矩阵的允许位置，以便行的总和等于给定的向量？
https://stackoverflow.com/questions/26704665
复制相似问题
腾讯云开发者
