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

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 所建议的那样，合并无限列表的无限列表是一种解决方案，但细节决定成败。

diagonal function from the universe-base 包可以做到这一点，所以你可以这样写：

import Data.Universe.Helpers

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

注意 - 这不满足您的排序标准，但我提到它是因为了解该包中的函数很有用，并且正确实现像 diagonal 这样的函数并不容易。

如果您想自己编写，请考虑将无限网格 N x N（其中 N 是自然数）分解为对角线：

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

并过滤此列表。

Answer 3

根据 Richard Bird 的 Thinking Functionally in Haskell 第 9 章，这里有一个可能的解决方案：

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 就可以了。

注意：此解决方案似乎比 Carsten "naive" 答案慢显着（大约 2 个数量级）。因此，如果您对性能感兴趣，我建议避免这种情况。然而，它仍然是一种有趣的方法，在其他情况下可能会有效。

Answer 4

I need to generate infinite sorted list of all coprimes. The first element in each pair must be less than the second. The sorting must be done in ascending order -- by the sum of pair's elements; and if two sums are equal, then by the pair's first element.

因此，我们生成了和和第一个元素的升序对，并且只保留互素数。简单俗气！

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

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

Generating sorted list of all possible coprimes

sorting

primes

haskell

list

infinite