You need to enable JavaScript to run this app. Haskell实现首尾固定、元素对等的Mul/Dup组合列表筛选与性能优化
优惠活动
大模型
产品
解决方案
定价
更多

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)会出现组合数量爆炸的问题——大部分生成的列表从一开始就不符合约束,属于无效计算。
更高效的思路是不要生成全量组合,直接生成满足所有约束的列表,在生成阶段就剪掉不符合要求的分支,核心是把所有约束提前拆解,避免冗余生成:

  1. 先梳理所有硬性约束:
    • 列表总长度为n,必须满足n为偶数、且n>=2,否则直接返回空结果
    • 开头固定是Dup,结尾固定是Mul
    • 全列表中Dup和Mul的总数相等,即各占n/2个
  2. 拆解剩余生成量:
    • 开头用掉1个Dup名额,结尾用掉1个Mul名额,剩下需要生成的中间段长度为n-2
    • 中间段里需要放的Dup数量为n/2 -1,剩余位置全放Mul
      这个拆解后,需要生成的列表总量是组合数C(n-2, n/2 -1),远小于全量的2^n。

你可以用带剪枝的递归生成器直接产出符合计数要求的中间段,不需要遍历无效分支:

-- 递归生成所有长度为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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.13 19:54:06