在Python中遍历斯特恩-布罗科特树的部分节点

Question

我的目标是遍历一对对的数字 [a,b]，要求 a 和 b 互质，并且 a+b 小于等于 n。比如说，如果 n=8，我想遍历的对包括 [1, 2]、[2, 3]、[3, 4]、[3, 5]、[1, 3]、[2, 5]、[1, 4]、[1, 5]、[1, 6]、[1, 7]。
我最初的想法是用递归函数来实现，利用 Stern-Brocot 树：

def Stern_Brocot(n,a=0,b=1,c=1,d=1):
if(a+b+c+d>n):
    return 0
x=Stern_Brocot(n,a+c,b+d,c,d)
y=Stern_Brocot(n,a,b,a+c,b+d)
if(x==0):
    if(y==0):
        return [a+c,b+d]
    else:
        return [a+c]+[b+d]+y
else:
    if(y==0):
        return [a+c]+[b+d]+x
    else:
        return [a+c]+[b+d]+x+y

正如预期的那样，

>>> Stern_Brocot(8)
[1, 2, 2, 3, 3, 4, 3, 5, 1, 3, 2, 5, 1, 4, 1, 5, 1, 6, 1, 7]

对于 n 小于等于 995 的情况，这个方法运行得很好。但当 n 大于等于 996 时，就出现了这个错误：

Traceback (most recent call last):
  File "<pyshell#17>", line 1, in <module>
    a=Stern_Brocot(996)
  File "C:\Users\Pim\Documents\C Programmeren en Numerieke Wisk\Python\PE\PE127.py", line 35, in Stern_Brocot
    y=Stern_Brocot(n,a,b,a+c,b+d)
...
  File "C:\Users\Pim\Documents\C Programmeren en Numerieke Wisk\Python\PE\PE127.py", line 35, in Stern_Brocot
    y=Stern_Brocot(n,a,b,a+c,b+d)
RuntimeError: maximum recursion depth exceeded in comparison

因为我想让 n 等于 120000，所以这个方法就不行了。 所以我的问题是：有没有什么好的方法可以遍历 Stern-Brocot 树的部分？（如果有其他方法可以遍历互质的整数，那也很好）。

Answer 1

在定义 Stern_Brocot 之前，先加上 sys.setrecursionlimit(120000)。这样做是为了把程序的递归调用限制设置为120000。

所以，你可以这样做：

import sys
sys.setrecursionlimit(120000)

def Stern_Brocot(n,a=0,b=1,c=1,d=1):
    if(a+b+c+d>n):
        return 0
    x=Stern_Brocot(n,a+c,b+d,c,d)
    y=Stern_Brocot(n,a,b,a+c,b+d)
    if(x==0):
        if(y==0):
            return [a+c,b+d]
        else:
            return [a+c]+[b+d]+y
    else:
        if(y==0):
            return [a+c]+[b+d]+x
        else:
            return [a+c]+[b+d]+x+y

Answer 2

这里有一个非递归的实现方式

def Stern_Brocot(n):
    states = [(0, 1, 1, 1)]
    result = []
    while len(states) != 0:
        a, b, c, d = states.pop()
        if a + b + c + d <= n:
            result.append((a+c, b+d))
            states.append((a, b, a+c, b+d))
            states.append((a+c, b+d, c, d))
    return result