查找所有可能的选项

Question

我需要找到所有等于给定的平方数的平方子集。ex：

f（11^2） - ＆gt; F（121） - ＆GT; [1,2,4,10]，[2,6,9]所有平方的总和等于121。

首先，我试图找到所有可能的总和的组合，即给定数字的总和。代码i尝试了

squares x = map (\x -> x * x ) [1..x]

--Using Subsequences,to create [subsequences][1] of the list

f n = filter (\x -> sum x == n) (subsequences.map (\y -> y *y) $ [1..(sqrt n)])

大量的序列会产生巨大的列表 ex：f（50^2）需要很长时间。还有其他方法可以有效进行吗？

Answer 1

假设我们要以降序从50个最低的正方形值中挑选，从此列表开始：[2500，2401，...，16，16，9，4，1]并

以 2500为目标。代码>子序列基于基于的算法是它将生成和测试所有 value子序列。例如，以[49*49，48*48]开头测试子序列是毫无意义的，因为49*49 + 48*48 = 4705＆gt; 2500。

子序列基于基于的算法不维护运行总和，也称为累加器。将子序列视为虚拟树，累加器使您可以一次消除树的整个分支，而不必检查树的所有可能的叶子。

可以编写一种递归算法，该算法维护部分总和。首先，我们需要一个辅助函数：

import  Data.List  (tails, subsequences)

getPairs :: [a] -> [(a,[a])]
getPairs xs = map (\(x:xs) -> (x,xs)) $ filter (not . null) $ tails xs

用法：

$ ghci
GHCi, version 8.8.4: https://www.haskell.org/ghc/  :? for help
...
 λ> 
 λ> printAsLines xs = mapM_  (putStrLn . show)  xs
 λ> 
 λ> printAsLines $ getPairs $ reverse $ map (^2) [1..8]
 (64, [49,36,25,16,9,4,1])
 (49, [36,25,16,9,4,1])
 (36, [25,16,9,4,1])
 (25, [16,9,4,1])
 (16, [9,4,1])
 (9,  [4,1])
 (4,  [1])
 (1,  [])
 λ> 
 λ> 
                 (Note: edited for readability)

上方，每对的左元素是要添加到运行和的元素，而正确的元素是剩余值列表，仍然可以考虑添加。

因此，我们可以为部分总和提供一般的递归算法：

getSummations :: Int -> [Int] -> [[Int]]
getSummations s xs = go [] 0 xs
    where
      -- go prefix runningSum restOfValues
      go prefix acc ys
         |  (acc >  s)  =  []         -- all rejected
         |  (acc == s)  =  [prefix]   -- cannot add further values
         |  otherwise   =
              let  pairs = getPairs ys
              in   concat $ map  (\(k,zs) -> go (k:prefix) (acc+k) zs)  pairs
              --  or: concatMap  (\(k,zs) -> go (k:prefix) (acc+k) zs)  pairs

前缀是求和中已经包含的值列表，s是目标总和。

请注意，“死分支”的修剪是由以下几行完成的：

         |  (acc >  s)  =  []         -- all rejected
         |  (acc == s)  =  [prefix]   -- cannot add further values

接下来，我们可以为我们的正方形值专业化机制：

getSquareSummations :: Int -> [[Int]]
getSquareSummations n = getSummations  (n*n)  (reverse $ map (^2) [1..n])

为了进行比较，子序列基于基于的算法可以像这样写：

naiveGetSquareSummations :: Int -> [[Int]]
naiveGetSquareSummations n = let  xss = subsequences $ map (^2) [1..n]
                             in   filter  (\xs -> sum xs == n*n)  xss

将GHC V8.8.4与-O2一起使用，表达式getsquaresummations 50将91021的列表返回可能的子序列，总计为2500，不到一秒钟。这是一个古董2014 Intel X86-64 CPU，Intel（R）Core（TM）i5-4440 @ 3.10GHz。