作者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/m.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