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

I am trying to solve a codewars problem :https://www.codewars.com/kata/54eb33e5bc1a25440d000891/train/haskell

First I tried to find all the possible combinations of sums that is equal sum of given number.Code that I have tried

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

But Sequences of a big number produces huge list Ex: f (50^2) takes long time.Is there is any other approach to proceed efficiently?

CodePudding user response：

Let's say we want to pick from the 50 lowest square values in descending order, starting with this list: [2500, 2401, ... , 16, 9, 4, 1] and targeting a sum of 2500.

The problem with your subsequences-based algorithm is that it is going to generate and test all value subsequences. But it is for example pointless to test subsequences starting with [49*49, 48*48], because 49*49 48*48 = 4705 > 2500.

The subsequences-based algorithm does not maintain a running sum, also known as an accumulator. Considering the subsequences as a virtual tree, an accumulator allows you to eliminate whole branches of the tree at once, rather than having to check all possible leaves of the tree.

It is possible to write a recursive algorithm which maintains an accumulator for the partial sum. First, we need an auxiliary function:

import  Data.List  (tails, subsequences)

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

Usage:

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

Above, the left element of each pair is the element to be added to the running sum, while the right element is the list of remaining values that can still be considered for addition.

We can thus provide a general recursive algorithm for partial sums:

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

Here, prefix is the list of values already included in the summation, and s is the target sum.

Note that the pruning of “dead branches” is done by the following lines:

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

Next, we can specialize the mechanism for our square values:

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

For comparison purposes, the subsequences-based algorithm can be written like this:

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

Using GHC v8.8.4 with -O2, the expression getSquareSummations 50 returns the list of 91021 possible subsequences summing to 2500, in less than one second. This is with a vintage 2014 Intel x86-64 CPU, Intel(R) Core(TM) i5-4440 @ 3.10GHz.