作者gecer (gecer)
看板Programming
標題Re: [討論] 排列組合的演算法解題
時間Sun Aug 1 21:45:46 2021
※ 引述《SocketAM2 (AM2)》之銘言：
: 基本想法是一個個位數iterate過去
: 有個簡單的剪枝手段：不可能達成4個的時候就不用往下數了
: 例如10000xx，最多就3個數
: 再來是個簡單的算小計手段：已經數到四個數了，剩下的位數只能在已知最大值之內
: 例如1234xyz中的xyz各能在(0,1,2,3,4)中任選，所以這類共5^3=125個
: 我試了下python，光用上面這兩招沒特別雕語法
: 大概可以跑在一秒多
: 原po可以參考看看
: 還有版友想得到其他有效手段嗎？
: 剛剛又發現一個不錯的手段：建表查表
: 例如前面算過1234xyz這類共125個
: 建個表，key是“ 前四位數最大為4，且已經數到4個數了”，值是125
: 以後再碰到這種case就直接小計125
: 遇到表上沒有的就往下拆分算完再加進表內
: 加上這招可以壓到0.03秒左右
小弟目前遇到同樣的問題 不過小弟的狀況是排列組合預估會有6^200 有可能記憶體不夠
或是計算時間過於長久 不曉得有沒有加速的方法
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.143.155.71 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Programming/M.1627825548.A.717.html
1F：推 LPH66: 題目放上來看看? 因為所謂的「剪枝」(排除 180.177.0.237 08/01 22:36
2F：→ LPH66: 不可能的選擇) 是會非常依賴於實際題目 180.177.0.237 08/01 22:37
3F：→ LPH66: 沒有實際題目的話只能和你說盡量剪 180.177.0.237 08/01 22:37
4F：→ LPH66: 但要怎麼剪我們是完全無法知道的 180.177.0.237 08/01 22:38
題目如下
https://ibb.co/kSGwmyk
用左邊的6個正方形(1~6)pattern將右邊的grid(20x10)填滿 每一次填入至少含一個
pattern的正方形(如N.4,只填5) grid不可重複填 要畫出所有排列組合並求最小填入
次數 初步考慮每個grid有可能被pattern的(1~6)正方形填入 估計大約<6^200種組合
※ 編輯: gecer (220.143.155.71 臺灣), 08/02/2021 20:45:34
※ 編輯: gecer (220.142.223.39 臺灣), 08/04/2021 08:27:57