使用恒定空间迭代所有互质对？

Question

我可以按照维基百科上列出的三元树算法生成所有互质对:https: //en.wikipedia.org/wiki/Coprime_integers

很快:

Start with two coprime branches: (2,1), (3,1), then iterate:
Branch 1: (2m-n,m)
Branch 2: (2m+n,m)
Branch 3: (m+2n,n)

然而,对于每对产生的空间使用的空间将增长三倍(并且说打印,或者不保留在存储器中).

这可能是haskell中的一个解决方案: 生成所有可能的coprimes的排序列表

但我正在寻找python中的东西,它没有懒惰的评估或无限的列表.

Answer 1

这使用对数空间,也许这足够好了？它是线性时间(使用O(k)时间来产生前k对).

def coprimes():
    yield (2, 1)
    yield (3, 1)
    for m, n in coprimes():
        yield (2*m - n, m)
        yield (2*m + n, m)
        yield (m + 2*n, n)

您可以在David Eppstein的这些文章中阅读有关此类自递归生成器的更多信息:

• 树的宽度第一次遍历(Python配方)
• 自递归生成器(Python配方)
• Kolakoski树

演示前20对:

>>> pairs = coprimes()
>>> for _ in range(20):
        print(next(pairs))

(2, 1)
(3, 1)
(3, 2)
(5, 2)
(4, 1)
(5, 3)
(7, 3)
(5, 1)
(4, 3)
(8, 3)
(7, 2)
(8, 5)
(12, 5)
(9, 2)
(7, 4)
(9, 4)
(6, 1)
(7, 5)
(13, 5)
(11, 3)

演示显示第十亿对,这需要我的PC大约4分钟,而Python进程的内存使用率保持在任何Python进程至少占用我的9.5 MB基线.

>>> from itertools import islice
>>> next(islice(coprimes(), 10**9-1, None))
(175577, 63087)