Re: [中學] 不重複的排列組合

[Desperato (Farewell)]

※ 引述《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://www.ptt.cc/bbs/Math/M.1471797891.A.FDF.html
→ Desperato   : 是說原本打算等程式跑出無解後認真去看w大的解釋...
※ 編輯: Desperato (101.12.133.85), 08/22/2016 01:19:22
推 bfl821002   : 可以分享是用什麼程式跟程式碼嗎？
推 bfl821002   : 如果11,12不碰到 還排的出這麼漂亮的組合嗎
→ Desperato   : 就一般的 Dev C++ ...
→ Desperato   : 例如9和12沒碰到 你就把所有9和11交換一下就好
→ Desperato   : 話說 可行組合超多種 我跑了幾百組之後懶得跑了