作者qiaffvvf (鸑鷟)
看板MJ_JP
标题[闲聊] 麻将比赛尽量不重覆对手的赛程排法
时间Tue Feb 23 11:54:16 2016
有点off-topic, 所以直接给结果
16人最多可以打五场, 每个人都不重覆对上 (两个参考解)
16/5 240(best) (每串是一场, 从前面开始每四个数字配在一组, 以此类推)
match 0
{ 12,5,13,10,7,9,6,8,3,0,11,14,2,1,4,15 }
match 1
{ 12,3,7,1,5,14,9,4,13,15,11,6,8,10,0,2 }
match 2
{ 9,1,11,10,6,2,12,14,3,15,5,8,0,13,7,4 }
match 3
{ 8,13,1,14,15,9,12,0,4,3,10,6,2,11,5,7 }
match 4
{ 4,12,8,11,14,7,10,15,1,6,0,5,2,13,9,3 }
match 0
{ 5,11,15,3,14,7,6,0,12,9,10,8,13,4,2,1 }
match 1
{ 8,13,6,15,9,14,5,1,4,3,7,12,10,11,2,0 }
match 2
{ 15,10,14,4,0,13,3,9,2,12,6,5,1,8,7,11 }
match 3
{ 9,7,15,2,12,13,14,11,8,0,5,4,1,3,10,6 }
match 4
{ 8,14,3,2,10,5,13,7,6,4,11,9,15,0,12,1 }
而32人打8场 目前还没找出不重覆对上的解, 但是有不错的排法(尽量不会重覆到)
32/8 788
match 0
{
5,23,20,27,15,3,31,16,26,13,30,19,6,2,24,17,11,22,9,21,8,1,4,7,12,10,29,18,25,28,0,14
}
match 1
{
8,24,9,19,15,14,21,30,29,26,5,31,12,16,23,1,3,20,0,11,25,18,4,17,7,6,27,28,10,2,13,22
}
match 2
{
6,8,30,11,25,24,27,10,15,1,13,28,7,0,5,12,18,19,20,16,29,21,23,17,4,22,3,26,2,14,31,9
}
match 3
{
21,20,4,31,6,26,9,25,1,22,19,29,7,15,5,17,18,13,3,27,28,30,2,12,16,11,24,14,10,0,8,23
}
match 4
{
30,25,31,16,13,14,6,4,10,17,8,20,27,0,9,1,29,11,2,7,22,28,24,5,18,23,15,26,12,3,19,21
}
match 5
{
2,16,0,4,27,15,29,8,9,17,12,22,3,30,24,1,6,21,18,5,13,11,25,23,20,14,26,7,28,10,31,19
}
match 6
{
2,3,8,5,15,25,12,20,22,6,23,31,24,18,30,0,16,7,13,21,28,29,9,4,10,11,26,1,17,27,14,19
}
match 7
{
25,2,21,1,20,24,29,13,12,11,31,27,14,18,22,8,9,23,7,3,4,30,10,5,0,15,19,6,16,28,26,17
}
重覆对上次数表
0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 0 0 1 1 1 0 1 1 0 1 0
1 0 1 1 1 0 0 1 1 1 1 1 1 1 0 1 1 0 0 1 0 1 1 1 1 1 1 1 1 1 1 0
1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 0 0 1 1 0 1 1 0 0 1 1 1 1
1 1 1 0 1 1 0 1 1 1 0 1 1 1 0 1 1 0 1 1 1 1 1 1 1 0 1 1 0 0 1 1
1 1 1 1 0 1 1 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 1 1 0 1 1 1 1
1 0 1 1 1 0 1 2 1 0 1 0 1 0 0 1 0 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1
1 0 1 0 1 1 0 1 1 1 0 1 0 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1
1 1 1 1 1 2 1 0 1 1 0 1 1 1 1 1 1 1 0 0 1 1 0 1 0 0 1 1 1 1 0 0
1 1 1 1 1 1 1 1 0 1 2 1 0 0 1 1 0 1 1 1 1 0 1 1 1 0 0 1 0 1 1 0
1 1 1 1 1 0 1 1 1 0 0 1 1 0 1 0 0 1 0 1 0 1 2 1 1 1 1 1 1 1 0 1
1 1 1 0 1 1 0 0 2 0 0 1 1 1 0 0 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1
1 1 1 1 0 0 1 1 1 1 1 0 1 1 1 0 1 0 0 0 1 1 1 1 1 1 1 1 0 1 1 1
1 1 1 1 0 1 0 1 0 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1
0 1 1 1 1 0 1 1 0 0 1 1 0 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0
1 0 1 0 1 0 1 1 1 1 0 1 0 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1
1 1 0 1 0 1 1 1 1 0 0 0 1 1 1 0 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 1
1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 0 1 0 1 2
0 0 1 0 1 1 1 1 1 1 1 0 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0
1 0 0 1 1 1 1 0 1 0 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 0
1 1 0 1 0 0 1 0 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 0 1 0 1 1 1 1 1 1
1 0 0 1 1 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 0 1 0 1
0 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 0 1 0 0 0 1 1 1
0 1 1 1 1 1 1 0 1 2 1 1 1 1 1 0 0 1 1 1 0 1 0 1 1 0 1 0 1 1 0 1
1 1 0 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 0 0 1 1 1 0 1 0 1
1 1 1 1 0 1 1 0 1 1 1 1 0 1 1 0 1 1 1 1 1 0 1 0 0 1 0 1 1 1 2 0
1 1 1 0 1 0 1 0 0 1 1 1 1 1 1 1 1 1 1 0 1 1 0 1 1 0 1 1 1 0 1 1
0 1 0 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 0 1 0 0 1 1 1 1
1 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 0 1 1 1 0 0 1 1 0 1
1 1 1 0 1 1 1 1 0 1 1 0 1 1 1 1 1 1 0 1 0 0 1 0 1 1 1 1 0 1 1 1
0 1 1 0 1 1 0 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 1 1 0 1 1 1 0 0 1
1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 1 0 1 1 0 1 0 0 2 1 1 0 1 0 0 1
0 0 1 1 1 1 1 0 0 1 1 1 1 0 1 1 2 0 0 1 1 1 1 1 0 1 1 1 1 1 1 0
如果32人要打7场的话..
32/7 672(最佳解 还满好找的 应该不少排法)
match 0
{
19,10,22,18,25,1,23,4,13,31,8,29,30,0,24,14,17,3,28,27,21,12,2,26,6,16,5,20,9,11,15,7
}
match 1
{
25,7,12,6,11,27,16,22,8,23,5,10,17,15,31,24,9,19,14,13,28,21,29,4,3,2,0,18,26,30,1,20
}
match 2
{
14,11,29,12,25,19,28,5,13,24,18,16,10,15,1,3,30,8,7,27,26,23,31,0,20,21,22,17,2,6,9,4
}
match 3
{
29,7,23,17,16,2,30,28,8,0,11,1,4,12,19,15,20,27,10,13,31,18,14,6,5,9,24,21,22,26,3,25
}
match 4
{
10,31,21,30,29,3,6,24,15,28,13,26,4,7,22,0,20,11,25,18,1,14,5,27,9,23,12,16,2,8,19,17
}
match 5
{
24,26,4,8,19,31,3,11,17,0,12,13,23,21,27,6,1,22,28,9,15,30,18,5,2,7,14,20,25,16,29,10
}
match 6
{
10,11,26,6,21,1,18,7,8,14,15,16,23,22,2,24,29,0,27,19,3,4,13,5,12,28,31,20,17,30,9,25
}
0 1 1 1 1 0 0 1 1 0 0 1 1 1 1 0 0 1 1 1 0 0 1 1 1 0 1 1 0 1 1 1
1 0 0 1 1 1 0 1 1 1 1 1 0 0 1 1 0 0 1 0 1 1 1 1 0 1 1 1 1 0 1 0
1 0 0 1 1 0 1 1 1 1 0 0 1 0 1 0 1 1 1 1 1 1 1 1 1 0 1 0 1 0 1 0
1 1 1 0 1 1 1 0 0 0 1 1 0 1 0 1 0 1 1 1 0 0 1 0 1 1 1 1 1 1 0 1
1 1 1 1 0 1 1 1 1 1 0 0 1 1 0 1 0 0 0 1 0 1 1 1 1 1 1 0 1 1 0 0
0 1 0 1 1 0 1 0 1 1 1 0 0 1 1 1 1 0 1 1 1 1 0 1 1 1 0 1 1 0 1 0
0 0 1 1 1 1 0 1 0 1 1 1 1 0 1 0 1 0 1 0 1 1 0 1 1 1 1 1 0 1 0 1
1 1 1 0 1 0 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 1 1 0 1 0 1 0 1 1 0
1 1 1 0 1 1 0 1 0 0 1 1 0 1 1 1 1 1 0 1 0 0 0 1 1 0 1 1 0 1 1 1
0 1 1 0 1 1 1 1 0 0 0 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 0 0 1 0 1 0
0 1 0 1 0 1 1 0 1 0 0 1 0 1 0 1 1 0 1 1 1 1 1 1 0 1 1 1 0 1 1 1
1 1 0 1 0 0 1 1 1 1 1 0 1 0 1 1 1 0 1 1 1 0 1 0 0 1 1 1 0 1 0 1
1 0 1 0 1 0 1 1 0 1 0 1 0 1 1 1 1 1 0 1 1 1 0 1 0 1 1 0 1 1 0 1
1 0 0 1 1 1 0 0 1 1 1 0 1 0 1 1 1 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1
1 1 1 0 0 1 1 1 1 1 0 1 1 1 0 1 1 0 1 1 1 0 0 0 1 0 0 1 0 1 1 1
0 1 0 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 0 0 0 0 1 0 1 0 1 0 1 1
0 0 1 0 0 1 1 0 1 1 1 1 1 1 1 1 0 0 1 0 1 0 1 1 1 1 0 1 1 1 1 0
1 0 1 1 0 0 0 1 1 1 0 0 1 1 0 1 0 0 0 1 1 1 1 1 1 1 0 1 1 1 1 1
1 1 1 1 0 1 1 1 0 0 1 1 0 1 1 1 1 0 0 1 1 1 1 0 1 1 0 0 0 0 1 1
1 0 1 1 1 1 0 0 1 1 1 1 1 1 1 1 0 1 1 0 0 0 1 0 0 1 0 1 1 1 0 1
0 1 1 0 0 1 1 1 0 0 1 1 1 1 1 0 1 1 1 0 0 1 1 0 0 1 1 1 1 0 1 1
0 1 1 0 1 1 1 1 0 1 1 0 1 0 0 0 0 1 1 0 1 0 1 1 1 0 1 1 1 1 1 1
1 1 1 1 1 0 0 1 0 1 1 1 0 0 0 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 0 0
1 1 1 0 1 1 1 1 1 1 1 0 1 0 0 0 1 1 0 0 0 1 1 0 1 1 1 1 0 1 0 1
1 0 1 1 1 1 1 0 1 1 0 0 0 1 1 1 1 1 1 0 0 1 1 1 0 0 1 0 0 1 1 1
0 1 0 1 1 1 1 1 0 1 1 1 1 0 0 0 1 1 1 1 1 0 1 1 0 0 1 0 1 1 1 0
1 1 1 1 1 0 1 0 1 0 1 1 1 1 0 1 0 0 0 0 1 1 1 1 1 1 0 0 1 0 1 1
1 1 0 1 0 1 1 1 1 0 1 1 0 1 1 0 1 1 0 1 1 1 1 1 0 0 0 0 1 1 1 0
0 1 1 1 1 1 0 0 0 1 0 0 1 1 0 1 1 1 0 1 1 1 1 0 0 1 1 1 0 1 1 1
1 0 0 1 1 0 1 1 1 0 1 1 1 1 1 0 1 1 0 1 0 1 0 1 1 1 0 1 1 0 0 1
1 1 1 0 0 1 0 1 1 1 1 0 0 0 1 1 1 1 1 0 1 1 0 0 1 1 1 1 1 0 0 1
1 0 0 1 0 0 1 0 1 0 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 0 1 0 1 1 1 0
36/7 756
match 0
{
8,31,10,21,4,22,33,9,34,0,11,19,18,30,15,6,27,5,13,17,32,20,16,29,35,2,3,7,24,23,26,28,1,14,25,12
}
match 1
{
28,10,30,2,25,7,5,20,11,6,12,27,35,23,29,14,4,31,19,24,17,21,32,22,1,8,13,15,26,33,34,16,0,3,9,18
}
match 2
{
25,32,2,15,3,5,10,11,22,34,23,8,16,0,14,21,9,28,13,19,35,33,27,1,31,20,18,17,7,24,30,12,4,29,26,6
}
match 3
{
2,11,13,24,16,27,28,25,14,8,33,6,4,21,20,30,10,7,0,23,19,22,18,29,1,32,31,26,34,3,17,12,9,5,35,15
}
match 4
{
35,13,21,6,15,19,16,3,10,24,22,1,31,25,29,30,26,7,18,8,33,11,32,28,2,17,9,23,14,27,20,34,4,5,0,12
}
match 5
{
11,31,35,16,33,23,15,20,3,6,22,28,25,26,19,21,4,7,1,17,5,24,18,14,32,34,30,9,12,13,10,29,0,2,8,27
}
match 6
{
15,14,22,31,9,11,20,26,13,4,23,3,34,6,5,1,28,7,21,29,0,33,17,30,35,24,8,25,16,18,2,12,27,10,19,32
}
使用的方式是启发式演算法程式暴力搜寻 随机起点 单用greedy找local optimal
到达local optimal之後不作跳出山谷的处理, 直接重新随机一个起点做下去
再从暂时的结果里面挑一个看起来比较顺眼的
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 118.163.30.37
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/MJ_JP/M.1456199659.A.510.html
1F：推 zxp86218: 快推不然别人以为我看不懂 02/23 11:59
加注
2F：推 Starflyx: 不愧是练ACM出来的 02/23 12:30
漏了32/7 补上
※ 编辑: qiaffvvf (118.163.30.37), 02/23/2016 14:54:51
3F：推 funliung: 吐了，有点晕车的感觉 02/23 16:15
4F：→ qiaffvvf: 对不起QQ 02/23 17:10
5F：推 solitaire27: 看久了觉得我好像不认识阿拉伯数字了... 02/23 17:15
6F：推 Bingojkt: 推，16人5场的我曾经手动排过，32人就没想过了XD 02/23 23:49
8F：推 bluefancy: 太复杂了吧.. 02/24 14:39
补36/7
※ 编辑: qiaffvvf (118.163.30.37), 02/26/2016 21:01:50
9F：推 Bingojkt: 要排赛程让每个选手都平均对到的条件有两个 若总人数为n 02/27 09:01
10F：→ Bingojkt: 则满足1.n是4的倍数 2.n-1是3的倍数 就可以办到 02/27 09:01
11F：→ Bingojkt: 联立解出4+12n，所以4人，16人，28人，40人都可以公平排 02/27 09:02
12F：→ Bingojkt: 不过没考虑选手相性问题 其他数字的话只能大概逼近而已 02/27 09:04
可以说解「可能存在」, 但是排不排得出又是另一回事
4和16有解 28我刚才跑了一下目前还没找到最佳解
排法好坏的参考计算法是取每个人对到其他人次数平方的总和
28人9场最佳=28人*9场*每场3人=756
这边程式跑一分钟左右只找到880,
虽然算法上还有再修改的空间, 但是这个差距我会倾向假设它没有完全不重覆的解存在
28/9 880
match 0
{ 1,23,26,7,21,19,0,4,10,17,11,18,16,22,3,27,2,24,15,25,12,5,20,13,8,14,9,6 }
match 1
{ 23,16,5,21,14,24,17,15,18,25,2,1,12,4,8,3,13,0,11,7,22,19,20,9,26,10,27,6 }
match 2
{ 25,5,26,9,10,12,24,21,6,0,23,20,7,4,22,18,19,3,2,14,15,11,16,1,27,13,17,8 }
match 3
{ 9,23,3,11,16,10,2,0,13,1,21,27,22,8,5,15,24,18,26,12,4,14,25,20,19,6,7,17 }
match 4
{ 7,12,2,27,0,14,26,16,8,18,22,23,20,21,25,17,4,10,1,9,6,3,13,15,19,24,5,11 }
match 5
{ 7,16,20,8,1,14,22,12,3,17,0,18,11,4,25,27,6,5,21,2,24,9,13,26,23,19,15,10 }
match 6
{ 21,3,26,22,8,20,2,11,19,23,25,12,17,0,5,1,7,14,13,10,9,18,27,15,24,16,6,4 }
match 7
{ 10,3,5,7,6,24,25,22,18,21,14,11,27,20,0,15,8,19,26,1,16,17,12,9,2,4,13,23 }
match 8
{ 10,0,8,25,20,24,1,3,6,12,11,22,27,23,5,14,19,18,13,16,4,26,2,17,9,15,7,21 }
0 1 1 1 1 1 1 1 1 0 2 1 0 1 1 1 2 2 1 1 2 1 0 1 0 1 1 1
1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1
1 1 0 1 2 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 2 1 1
1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 0 1 1
1 1 2 1 0 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 2 1 1
1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 2 1 2 1 1 1 1
1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 2 1 2 1 1 1
1 1 1 1 1 1 1 0 1 1 2 1 1 2 1 1 1 1 1 1 1 1 1 1 0 0 1 1
1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 2 0 2 1 0 1 1 1
0 1 0 1 1 1 1 1 1 0 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 2 1
2 1 1 1 1 1 1 2 1 1 0 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 2 1 1 1 1 1 1 1 0 1
0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 1 1 1 1 1 1 2 1 2 1 1 1
1 1 1 1 1 1 1 2 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 0 1 2
1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 0 1 1 1 1 2 1 1 0 1 1 0 1 1 1 1 1 1 1 1 2 1 0 2
2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1
2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 2 1 1 1 0 0 1 1 1 1
1 1 1 1 1 0 0 1 1 1 1 2 1 1 1 1 1 2 0 1 0 1 2 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 2 1 1 1 0
2 1 1 1 1 1 1 1 2 1 0 1 1 1 1 1 1 1 0 1 0 1 1 1 1 2 0 1
1 1 1 1 1 2 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1
0 1 0 2 1 1 2 1 2 1 0 1 2 0 1 1 1 0 2 1 1 1 0 1 1 1 1 1
1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 0 1 2 1 1 1 0 0 1 1 1
0 1 1 1 1 1 2 0 0 1 1 1 2 1 1 2 1 1 1 1 1 1 1 0 0 2 2 0
1 1 2 0 2 1 1 0 1 1 1 1 1 0 1 1 0 1 1 1 2 1 1 1 2 0 1 1
1 2 1 1 1 1 1 1 1 2 1 0 1 1 1 0 1 1 1 1 0 1 1 1 2 1 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 2 1 1 1 0 1 1 1 1 0 1 1 0
上面全部先平方再加起来是880 可以看到还是有很多重覆对上的情况
※ 编辑: qiaffvvf (220.133.36.109), 02/27/2016 13:12:42