背景:
我们麻将群准备举办一个麻将比赛,总共有 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 写了个实现,最后还是使用不同的待选池序列尝试了一千多万次才找出满足条件的结果。想问问有没有更好的办法
1
shinonome 302 天前
太复杂了吧,直接瑞士轮呗
|
3
zhaozhou 301 天前
也许第一步可以按照下表来安排每日出战的 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 次。 |
4
zhaozhou 300 天前
| |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 | |
5
zhaozhou 300 天前
| |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 . . . |
6
zhaozhou 300 天前
每一行都往右移动一格到下一个非零队伍开始组一个四人局
|
8
zhaozhou 299 天前
又推了几天,简单的平移确实不能保证两两只相遇四次
aGVqaWFAbnVtYWcubmV0 base64 进一步交流? |