list - 生成所有可能互素数的排序列表

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