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