有没有大佬帮我解答一个关于比赛分组的算法问题？

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 311 天前的主题，其中的信息可能已经有所发展或是发生改变。

背景：

我们麻将群准备举办一个麻将比赛，总共有 10 个队伍参赛，假设这 10 个队伍分别为 A,B,C,D,E,F,G,H,I,J ；

要求：

1 ，总共安排 30 场对战，每天两场，总共 15 天，每个队伍出战 12 次；每个队伍遇到其他每个队伍的次数相同，即任意两个队伍之间的相遇 4 次。

2 ，每天两场比赛同时进行，8 个队伍参赛，两个队伍轮空。每个队伍每天只能参加一场。

问题：如何安排每天的赛程？

我个人上班摸鱼的时候想了一些办法，虽然找到满足要求的结果了，但是觉得并不是最优解，所以来虚心请教下。

已知所有相遇可能性为 C10,2 = 45 ，每场对战的不同相遇数为 C4,2 = 6;

我使用的方法是，最后的结果使用一个二维数组来存放，每个元素代表每天的两场对战。例如：[[ABCD,EFGH],[ABCD,EFGH]...]。

每次挑选两个相遇来组合成一次对战。要求这两次相遇没有同一个队伍，并且如果本场对战是当天的第二场，还要先排除第一场已经参赛的队伍。先将总共 30*6 = 180 个相遇放到待选池中，每次从池中选择一个相遇时，优先选择最终结果中已选择的相遇次数最少的相遇来组成一场对战。

然后我用 js 写了个实现，最后还是使用不同的待选池序列尝试了一千多万次才找出满足条件的结果。想问问有没有更好的办法

相遇

队伍

对战

待选池

11 条回复 • 2024-01-31 09:34:46 +08:00

shinonome

311 天前

太复杂了吧,直接瑞士轮呗

Alalajiyh

311 天前

@shinonome 主办方要求要这么排，我只是想知道有没有什么好的方法来解决这个问题

zhaozhou

310 天前

也许第一步可以按照下表来安排每日出战的 8 支队伍:
| | A | B | C | D | E | F | G | H | I | J | SUM |
|----- |--- |--- |--- |--- |--- |--- |--- |--- |--- |--- |----- |
| D1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 8 |
| D2 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 8 |
| D3 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 8 |
| D2 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 8 |
| D5 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 8 |
| D6 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 8 |
| D7 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 8 |
| D8 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | 8 |
| D9 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 8 |
| D10 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 8 |
| D11 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 8 |
| D12 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 8 |
| D13 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 8 |
| D14 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 8 |
| D15 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 8 |

然后再保证 12 天的组合中同一支队伍出现不超过 4 次。

zhaozhou

310 天前

| |A | B | C | D | E | F | G | H | I | J |SUM|
|----- |--- |--- |--- |--- |--- |--- |--- |--- |--- |--- |-----|
| D1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 8 |
| D2 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 8 |
| D3 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 8 |
| D4 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 8 |
| D5 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 8 |
| D6 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 8 |
| D7 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 8 |
| D8 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | 8 |
| D9 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 8 |
| D10 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 8 |
| D11 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 8 |
| D12 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 8 |
| D13 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 8 |
| D14 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 8 |
| D15 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 8 |

zhaozhou

310 天前

| |A | B | C | D | E | F | G | H | I | J |
|----- |--- |--- |--- |--- |--- |--- |--- |--- |--- |--- |
| D1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | => BCDE, FGIJ
| D2 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | => CDEF, GHJB
| D3 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | => DEFG, HJCD
| D4 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | => EFGH, JACD
| D5 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | => FGHI, JADE
.
.
.

zhaozhou

309 天前

每一行都往右移动一格到下一个非零队伍开始组一个四人局

Alalajiyh

309 天前 via Android

@zhaozhou 好像是我没看懂？这个方法是如何保证每个队伍与任意队伍相遇的次数相同的

zhaozhou

309 天前

又推了几天，简单的平移确实不能保证两两只相遇四次
aGVqaWFAbnVtYWcubmV0
base64
进一步交流？

zhaozhou

309 天前

@Alalajiyh

Alalajiyh

307 天前 via Android

@zhaozhou 可以的，兄弟辛苦了

Alalajiyh

307 天前 via Android

@zhaozhou 这个是什么账号？还是邮箱吗？