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

Question

我需要生成所有副本的无限排序列表。 每对中的第一个元素必须小于第二个元素。 排序必须按升序排列 - 通过对元素的总和;如果两个和是相等的，那么通过这个对的第一个元素。

所以，在结果列表必须

[(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第一对。我意识到排序不能在无限列表上完成。

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

Answer 1

虽然可能不是最理想的方式，但如果您首先生成所有可能的对然后过滤它们，它应该可以工作。

因此，使用您的标准：

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的定义，甚至加入他们，但我在这里认为这是更明显发生了什么

Answer 2

正如@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) ] ++ ... 

和过滤此列表。

Answer 3

这里有以下理查德·伯德的的第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“幼稚”的答案慢。所以如果你对表演感兴趣，我建议避免这种情况。但它仍然是一个有趣的方法，可能在其他情况下有效。

Answer 4

我需要生成所有coprimes无限排序列表。每对中的第一个元素必须小于第二个元素。排序必须按照升序排列 - 通过对的元素总和;如果两个和是相等的，那么通过这个对的第一个元素。

因此，我们生成升序对和第一个元素，并且只保留coprimes。容易俗气！

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