生成所有可能的副本的排序列表

我需要生成所有副本的無限排序列表。每對中的第一個元素必須小於第二個元素。排序必須按升序排列 - 通過對元素的總和;如果兩個和是相等的，那麼通過這個對的第一個元素。生成所有可能的副本的排序列表

所以，在結果列表必須

[(2,3),(2,5),(3,4),(3,5),(2,7),(4,5),(3,7),(2,9),(3,8),(4,7)...`

這裏是我的解決方案。

coprimes :: [(Int, Int)] 
coprimes = sortBy (\t1 t2 -> if uncurry (+) t1 <= uncurry (+) t2 then LT else GT) $ helper [2..] 
    where helper xs = [(x,y) | x <- xs, y <- xs, x < y, gcd x y == 1]

問題是，我不能採取n第一對。我意識到排序不能在無限列表上完成。

但是我怎樣才能以懶惰的方式生成相同的序列？

來源

2015-11-14 tsmbl

這個技巧可能是爲'2'生成對，'3'爲升序並*合併*它們。 – Bakuriu

雖然可能不是最理想的方式，但如果您首先生成所有可能的對然後過濾它們，它應該可以工作。

因此，使用您的標準：

pairs :: [(Integer,Integer)] 
pairs = [ (i,l-i) | l <- [1..], i <- [1..l-1] ] 

coprimes :: [(Integer,Integer)] 
coprimes = [ (i,j) | (i,j) <- pairs, 1 < i, i < j,gcd i j == 1]

產生

λ> take 10 coprimes 
[(2,3),(2,5),(3,4),(3,5),(2,7),(4,5),(3,7),(2,9),(3,8),(4,7)]

現在當然你也可以把一些東西1 < i和i < j想到到pairs的定義，甚至加入他們，但我在這裏認爲這是更明顯發生了什麼

來源

2015-11-14 17:15:33 Carsten

正如@Bakuriu建議，合併無限的infini列表te清單是一個解決方案，但魔鬼是在細節。

從universe-base包中的diagonal功能可以做到這一點，那麼你可以寫：

import Data.Universe.Helpers 

coprimes = diagonal [ go n | n <- [2..] ] 
    where go n = [ (n,k) | k <- [n+1..], gcd n k == 1 ]

注 - 這不符合您的排序標準，但我說出來，因爲在該包的功能是有用的瞭解並正確實施diagonal這樣的功能並不容易。

如果你想編寫自己的，可以考慮分解無限電網的N×N（N是自然數）成對角線：

[ (1,1) ] ++ [ (1,2), (2,1) ] ++ [ (1,3), (2,2), (3,1) ] ++ ...

和過濾此列表。

來源

2015-11-14 17:20:08 ErikR

這裏有以下理查德·伯德的的第9章在Haskell功能思考一個可能的解決方案：

coprimes = mergeAll $ map coprimes' [2..] 

coprimes' n = [(n, m) | m <- [n+1..], gcd m n == 1] 

merge (x:xs) (y:ys) 
    | s x < s y = x:merge xs (y:ys) 
    | s x == s y = x:y:merge xs ys 
    | otherwise = y:merge (x:xs) ys 
    where s (x, y) = x+y 

xmerge (x:xs) ys = x:merge xs ys 

mergeAll = foldr1 xmerge

，其結果是：

> take 10 $ coprimes 
[(2,3),(2,5),(3,4),(3,5),(2,7),(4,5),(3,7),(2,9),(3,8),(4,7)]

注意的mergeAll自然的定義是foldr1 merge ，但這不起作用，因爲它會試圖在返回第一個元素之前找到所有列表中的第一個元素的最小值，因此您最終會處於無限循環。但是，由於我們知道列表按升序排列，而最小值是第一個列表中的第一個元素xmerge可以訣竅。

注：此溶液似乎是顯著（如2階量值的）比的Carsten「幼稚」的答案慢。所以如果你對錶演感興趣，我建議避免這種情況。但它仍然是一個有趣的方法，可能在其他情況下有效。

來源

2015-11-14 17:21:22 Bakuriu

我需要生成所有coprimes無限排序列表。每對中的第一個元素必須小於第二個元素。排序必須按照升序排列 - 通過對的元素總和;如果兩個和是相等的，那麼通過這個對的第一個元素。

因此，我們生成升序對和第一個元素，並且只保留coprimes。容易俗氣！

[ (first, second) 
| sum <- [3..] 
, first <- [2..sum `div` 2] 
, let second = sum-first 
, gcd first second == 1 
]

來源

2015-11-14 17:39:44

生成所有可能的副本的排序列表

回答

相關問題