Haskell实现首尾固定、元素对等的Mul/Dup组合列表筛选与性能优化
直接扩展现有筛选逻辑的实现
你可以直接在原有链式筛选的基础上,新增「Dup与Mul数量相等」的判断条件,不需要改动原有生成逻辑。
首先定义通用的计数函数,用来统计列表中某个指令的出现次数:
countOf :: Instruction -> [Instruction] -> Int countOf target = length . filter (== target)
因为你生成的列表仅由Dup、Mul构成,只要列表长度非空,就可以直接把三个筛选条件合并成单个判断,替换掉原来的嵌套filter写法。这里可以加一个前置快速判断优化:如果n是奇数,根本不可能实现Dup和Mul数量相等,可以直接跳过生成流程返回空列表,避免无效计算:
filteredResult | n < 2 || odd n = [] | otherwise = filter checkValid $ mapM (const [Mul, Dup]) [1..n] where checkValid xs = head xs == Dup -- 保留开头为Dup的列表 && last xs == Mul -- 保留结尾为Mul的列表 && countOf Dup xs == countOf Mul xs -- 保留两者数量相等的列表
针对大n值的高效实现方案
原有「先生成所有2^n种组合、再逐行筛选」的方式,在n较大时(比如n>=20)会出现组合数量爆炸的问题——大部分生成的列表从一开始就不符合约束,属于无效计算。
更高效的思路是不要生成全量组合,直接生成满足所有约束的列表,在生成阶段就剪掉不符合要求的分支,核心是把所有约束提前拆解,避免冗余生成:
- 先梳理所有硬性约束:
- 列表总长度为n,必须满足n为偶数、且n>=2,否则直接返回空结果
- 开头固定是
Dup,结尾固定是Mul - 全列表中
Dup和Mul的总数相等,即各占n/2个
- 拆解剩余生成量:
- 开头用掉1个
Dup名额,结尾用掉1个Mul名额,剩下需要生成的中间段长度为n-2 - 中间段里需要放的
Dup数量为n/2 -1,剩余位置全放Mul
这个拆解后,需要生成的列表总量是组合数C(n-2, n/2 -1),远小于全量的2^n。
- 开头用掉1个
你可以用带剪枝的递归生成器直接产出符合计数要求的中间段,不需要遍历无效分支:
-- 递归生成所有长度为remLen、恰好包含remDup个Dup的列表,剩余位置放Mul genMiddles :: Int -> Int -> [[Instruction]] genMiddles 0 0 = [[]] genMiddles remLen remDup -- 剪枝:需要的Dup数超出剩余长度、或者剩余Dup数为负时,直接返回空 | remDup < 0 || remDup > remLen = [] | otherwise = -- 分两种选择生成:当前位置放Dup / 当前位置放Mul map (Dup:) (genMiddles (remLen - 1) (remDup - 1)) ++ map (Mul:) (genMiddles (remLen - 1) remDup)
最后把生成的中间段和固定的开头、结尾拼接,就得到所有符合要求的列表:
efficientResult | n < 2 || odd n = [] | otherwise = let k = n `div` 2 middleLen = n - 2 middleDupCount = k - 1 middles = genMiddles middleLen middleDupCount in map (\mid -> [Dup] ++ mid ++ [Mul]) middles
拿题目中提到的n=4的场景验证:
- 计算得k=2,middleLen=2,middleDupCount=1
- 递归生成的中间段为
[Dup,Mul]、[Mul,Dup] - 拼接后得到结果
[Dup,Dup,Mul,Mul]、[Dup,Mul,Dup,Mul],和样例完全匹配。
两种方案的适用场景
- 当n较小(比如n<=16)时,直接用带前置奇偶判断的filter方案就足够,代码简洁易维护
- 当n较大时,使用带剪枝的约束生成方案,能避免组合爆炸问题,生成效率比全量过滤高几个数量级
内容的提问来源于stack exchange,提问作者Georgi Spasov
相关产品推荐
相关产品推荐

