的Haskell - 列表解析不能枚舉N×N

我必須寫一個函數，它返回所有對的列表（X，Y），其中x， ÿ∈N，和：的Haskell - 列表解析不能枚舉N×N

x是兩個自然數的乘積（X = A•b，其中A，b∈N）和
x是真的比5大，但確實小於500，和
y是正方形號碼（y = c 2，其中c∈N）不大於1000,和
x是y的除數。

我嘗試：

listPairs :: [(Int, Int)] 
listPairs = [(a*b, y) | y <- [0..], a <- [0..], b <- [0..], 
         (a*b) > 5, (a*b) < 500, (y*y) < 1001, 
         mod y (a*b) == 0]

但它不返回任何東西，電腦作品很多就可以了。

但是，如果我選擇較小的範圍爲a,b和y e。 G。 [0..400]，它需要一分鐘，但它返回正確的結果。

那麼我該如何解決性能問題呢？

來源

2013-05-14 John

-1你已經得到噸的幫助，請不要從網站到網站上尋求幫助（丹尼Gratzer） – jozefg

僅供參考，以那些不知道我在說什麼，這是由OP問及已經長今午（https://groups.google.com/forum/?fromgroups=#!topic/haskell-cafe/fK1jJ3SSaUE） – jozefg

'400'太低迴答。你應該確保你沒有錯過任何正確的解決方案：'（a * b）<500, (a*b)> 5，a == 1，b == 499'是一致的。所以使用'[1..499]'（'0 * x> 5'永遠不會）。 OTOH'（y * y）< 1001' ==>'y <32'所以使用'y < - [1..31]，a < - [1..499]'。應該讓它快32倍。然後，使用'b < - [a..min 499（div 500a）]''a * b <500'和'a * b == b * a'，這給我們帶來了另一個問題大小的減少。現在不到一秒鐘。 –

因此，在無限列表的過程中嵌套列表理解不終止。

幸運的是，您的列表並非無限。有一個限制。如果x = a*b < 500，那麼我們知道它必須是a < 500和b < 500。另外，c = y*y < 1001只是y < 32。所以，

listPairs :: [(Int, Int)] 
listPairs = 
    [(x, c*c) | c <- [1..31], a <- [1..499], -- a*b < 500 ==> b<500/a , 
       b <- [a..min 499 (div 500 a)], -- a*b==b*a ==> b >= a 
       let x = a*b, x > 5, 
       -- (a*b) < 500, (c*c) < 1001, -- no need to test this 
       rem (c*c) x == 0]

mod 0 n == 0平凡認爲，所以我從「自然數」這裏不包括0。

這裏仍然產生了一些重複的，即使我們在x=a*b限制b值b >= a，因爲x可以有多種表示（例如1*6 == 2*3）。您可以使用Data.List.nub擺脫它們。從哈斯克爾咖啡

來源

2013-05-21 15:32:34

的Haskell - 列表解析不能枚舉N×N

回答

相關問題