作者Desperato (Farewell)
看板Math
标题Re: [中学] 不重复的排列组合
时间Mon Aug 22 00:44:46 2016
※ 引述《bfl821002 (章鱼哥)》之铭言:
: 如图
: 总共有12队
: 请问能在这6*6的矩阵中
: (横项是关卡 纵项是时间)
: 所以不能纵向出现两个数字
: 尽量直向也不要重复出现数字
: (这样就是重复对战组合)
: 在这两个条件限制下能
: 排出不重复的对战组合吗?
: http://i.imgur.com/e7nQmif.jpg
抱歉来晚了ow o
这种东西我也不会用数学解,所以决定写程式
程式也很烂所以写了2小时...(撞墙
success!
( 1, 2) ( 3, 4) ( 5, 6) ( 7, 8) ( 9,10) (11,12)
( 3, 5) ( 1, 6) ( 2, 4) ( 9,11) ( 7,12) ( 8,10)
( 4, 6) ( 7,10) ( 8, 9) ( 1,12) ( 3,11) ( 2, 5)
( 7, 9) ( 8,12) (10,11) ( 4, 5) ( 2, 6) ( 1, 3)
( 8,11) ( 2, 9) ( 3,12) ( 6,10) ( 1, 5) ( 4, 7)
(10,12) ( 5,11) ( 1, 7) ( 2, 3) ( 4, 8) ( 6, 9)
check...
0 1 1 0 1 1 1 0 0 0 0 1
1 0 1 1 1 1 0 0 1 0 0 0
1 1 0 1 1 0 0 0 0 0 1 1
0 1 1 0 1 1 1 1 0 0 0 0
1 1 1 1 0 1 0 0 0 0 1 0
1 1 0 1 1 0 0 0 1 1 0 0
1 0 0 1 0 0 0 1 1 1 0 1
0 0 0 1 0 0 1 0 1 1 1 1
0 1 0 0 0 1 1 1 0 1 1 0
0 0 0 0 0 1 1 1 1 0 1 1
0 0 1 0 1 0 0 1 1 1 0 1
1 0 1 0 0 0 1 1 0 1 1 0
程式内容没什麽,就暴力测试而已
第一列有给定1~12,以及第二列第一个的(3, 5),WLOG
原本以为会跑不完,还特地写best result看最多只能跑到哪
结果精进一下效率就出来了...(虽然还是花了30秒有,烂演算法
check没啥必要,只是怕我自己写错 + 证明真的没重复
总之,很神奇的居然有\ow o/
=============================
对了,如果规定是1~6号对上7~12号的话,就会跑不出来喔
remain record! (34)
( 1, 7) ( 2, 8) ( 3, 9) ( 4,10) ( 5,11) ( 6,12)
( 2, 9) ( 3,12) ( 6,10) ( 5, 7) ( 4, 8) ( 1,11)
( 6, 8) ( 4,11) ( 5,12) ( 1, 9) ( 3,10) ( 2, 7)
( 5,10) ( 6, 7) ( 2,11) ( 3, 8) ( 1,12) ( 4, 9)
( 3,11) ( 1,10) ( 4, 7) ( 2,12) ( 6, 9) ( 5, 8)
( 4,12) ( 5, 9) ( 1, 8) ( 6,11) ( 0, 0) ( 0, 0)
fail!
上面是最後跑出的,最极限的结果,只能塞34个
同样有给定第一列初始值,第二列第一个(2, 9)
以及第二列第二个的第一座标只能是1或3 (都是WLOG)
(最後改成这样还要跑3分钟,没简化就要十几分钟了...)
--
嗯嗯ow o
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 101.12.133.85
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Math/M.1471797891.A.FDF.html
1F:→ Desperato : 是说原本打算等程式跑出无解後认真去看w大的解释... 08/22 00:46
※ 编辑: Desperato (101.12.133.85), 08/22/2016 01:19:22
2F:推 bfl821002 : 可以分享是用什麽程式跟程式码吗? 08/22 10:54
3F:推 bfl821002 : 如果11,12不碰到 还排的出这麽漂亮的组合吗 08/22 11:09
4F:→ Desperato : 就一般的 Dev C++ ... 08/22 16:04
5F:→ Desperato : 例如9和12没碰到 你就把所有9和11交换一下就好 08/22 16:04
6F:→ Desperato : 话说 可行组合超多种 我跑了几百组之後懒得跑了 08/22 16:15