我需要找到等于給定平方數的所有平方子集。例如：
f (11^2) --> f (121) --> [1,2,4,10],[2,6,9] 所有單個平方和等于 121。
首先，我試圖找到與給定數字相等的總和的所有可能組合。我嘗試過的代碼
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)需要很長時間。還有其他方法可以有效地進行嗎？
uj5u.com熱心網友回復：
假設我們要按降序從 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在不到一秒的時間內回傳 91021 個可能子序列的串列，總和為 2500。這是一個老式的 2014 Intel x86-64 CPU，Intel(R) Core(TM) i5-4440 @ 3.10GHz。
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/482703.html
標籤：哈斯克尔