生成所有可能的coprimes的排序列表 [英] Generating sorted list of all possible coprimes

问题描述

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

因此，结果列表必须是

  [（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（\\如果uncurry（+）t1 <= uncurry（+）t2 then LT else GT）$ helper [2 ..] 
其中helper xs = [（x，y） x<  -  xs，y<  -  xs，x< y，gcd xy == 1] 
  

问题是我不能把 n 第一对。我意识到排序不能在无限列表中完成。

但是我怎么能用懒惰的方式生成相同的序列？

解决方案

如果您首先生成所有可能的对并过滤它们，它可能不是最理想的方式。

所以使用你的标准：

pre $ code $ pairs $ [$（$ Integer）]
pairs = [（我，李）| l < - [1 ..]，i < - [1..l-1]]

coprimes :: [（Integer，Integer）]
coprimes = [（i ，j）| （i，j）< - 对，1<我，我< j，gcd ij == 1]

产生

 λ> （2,3），（2,5），（3,4），（3,5），（2,7），（4,5），（3,7）， （2,9），（3,8），（4,7）] 
  

你可以把一些东西放在 1<我和 i < j 让我想起了对定义，甚至加入了它们，但我想这里更明显是怎么回事

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.

So, the resulting list must be

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

Here's my solution.

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]

The problem is that I can't take n first pairs. I realize that sorting can't be done on infinite lists.

But how can I generate the same sequence in a lazy way?

解决方案

While probably not the most optimal way it should works if you first generate all possible pairs and then filter them.

So using your criteria:

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]

produces

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

now of course you can put some of the stuff 1 < i and i < j comes to mind into the pairs definition or even join them but I think here it's more obvious what's going on

这篇关于生成所有可能的coprimes的排序列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！