使用恒定空间迭代所有互质对？ [英] Iterate all coprime pairs using constant space?

问题描述

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

I can generate all coprime pairs by following the ternary-tree algorithm listed on wikipedia: 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)

但是，每生产一对（并说是印刷的或不保存在内存中的），使用的空间将增加三倍。

However the space used will grow by a factor of three for each pair produced (and say printed, or otherwise not kept in memory).

这可能是haskell的一种解决方案：
生成所有可能的互质数的排序列表

Here might be a solution in haskell: Generating sorted list of all possible coprimes

但是我在python中寻找东西，没有懒惰的求值或无限列表。

But I was looking for something in python, which does not have lazy evaluation or infinite lists.

推荐答案

这使用对数空间，也许够好吗？这是线性时间（使用O（k）时间产生前k对）。

This uses logarithmic space, maybe that's good enough? And it's linear time (uses O(k) time to produce the first k pairs).

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的这些文章中了解有关此类自递归生成器的更多信息：

You can read more about such self-recursive generators in these articles by David Eppstein:

• 树的宽度优先遍历（Python食谱）


• 自递归生成器（Python食谱）


• 科拉科斯基树

• Breadth first traversal of tree (Python recipe)
• Self-recursive generators (Python recipe)
• The Kolakoski tree

演示了前20对的演示：

Demo showing the first 20 pairs:

>>> 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)

演示显示 billionth 对的演示，这使我的PC 4分钟，而Python进程的内存使用保持在9.5 MB基准，这是任何Python进程至少都会占用我的时间。

Demo showing the billionth pair, which takes my PC about 4 minutes while the memory usage of the Python process stays at the 9.5 MB baseline that any Python process takes me at least.

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

这篇关于使用恒定空间迭代所有互质对？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！