查找等于给定数字平方的数字的平方和的所有可能选项

Question

我需要找到等于给定正方形的所有正方形子集 number.Ex:

f (11^2) --> f (121) --> [1,2,4,10],[2,6,9] 所有单个平方和等于 121.

首先，我试图找到所有可能的总和组合，这些总和等于我尝试过的给定 number.Code 的总和

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)])

但是大数的序列会产生巨大的列表例如：f (50^2) 需要很长时间time.Is有没有其他方法可以有效地进行？

Answer 1

假设我们要按降序从 50 个最小的平方值中选择，从这个列表开始：[2500, 2401, ... , 16, 9, 4, 1] 并且目标总和为 2500。

基于 subsequences 的算法的问题在于它将生成并测试所有值子序列。但是，例如测试以 [49*49, 48*48] 开头的子序列是没有意义的，因为 49*49 + 48*48 = 4705 > 2500.

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

可以编写一个递归算法来维护部分和的累加器。首先，我们需要一个辅助函数：

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

这里，prefix是已经包含在总和中的值列表，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])

为了比较，基于subsequences的算法可以这样写：

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

使用带有 -O2 的 GHC v8.8.4，表达式 getSquareSummations 50 returns 91021 个可能子序列的列表总和为 2500，不到一秒。这是老式 2014 Intel x86-64 CPU，Intel(R) Core(TM) i5-4440 @ 3.10GHz。

查找等于给定数字平方的数字的平方和的所有可能选项

Finding all possible options of Sums of squares of the numbers equal to square of a given number

haskell