Re: [讨论] 排列组合的算法解题

楼主: gecer (gecer)   2021-08-01 21:45:46
※ 引述《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 有可能内存不够
或是计算时间过于长久 不晓得有没有加速的方法

Links booklink

Contact Us: admin [ a t ] ucptt.com