Python有序生成马尔可夫数序列问题咨询，涉及yield与yield from用法

需求背景 #

我希望通过实践深入理解yield和yield from的用法，目标是按从小到大的顺序生成马尔可夫（Markov）数序列，序列第一个元素的索引为0。

现有实现代码 #

我编写的代码如下：

def chain(iter1, iter2):
    while True:
        yield next(iter1)
        yield next(iter2)

def isMarkov(x,y,z):
    if x**2 + y**2 + z**2 == 3 * x * y * z:
        return True
    else:
        return False

def gen_markov(seed):
    x1 = seed[0]
    y1 = seed[2]
    z1 = y1 + 1
    while not isMarkov(x1,y1,z1):
        z1 += 1
    yield (x1,y1,z1)
    
    x2 = seed[1]
    y2 = seed[2]
    z2 = y2 + 1
    while not isMarkov(x2,y2,z2):
        z2 += 1
    yield (x2,y2,z2)
    
    yield from chain(gen_markov((x1,y1,z1)), gen_markov((x2,y2,z2)))
    
def markov(n):
    g = gen_markov((1,2,5))
    markov_nums = set([1,2,5])
    while len(markov_nums) <= n:
        triple = next(g)
        for x in triple:
            markov_nums.add(x)
    markov_nums = list(markov_nums)
    markov_nums.sort()
    print(markov_nums[n])

n = int(input('Enter n: '))
markov(n)

上述代码可以以树状结构生成马尔可夫三元组，以下是gen_markov函数生成的前35个马尔可夫三元组：

(1, 5, 13)
(2, 5, 29)
(1, 13, 34)
(2, 29, 169)
(5, 13, 194)
(5, 29, 433)
(1, 34, 89)
(2, 169, 985)
(5, 194, 2897)
(5, 433, 6466)
(13, 34, 1325)
(29, 169, 14701)
(13, 194, 7561)
(29, 433, 37666)
(1, 89, 233)
(2, 985, 5741)
(5, 2897, 43261)
(5, 6466, 96557)
(13, 1325, 51641)
(29, 14701, 1278818)
(13, 7561, 294685)
(29, 37666, 3276509)
(34, 89, 9077)
(169, 985, 499393)
(194, 2897, 1686049)
(433, 6466, 8399329)
(34, 1325, 135137)
(169, 14701, 7453378)
(194, 7561, 4400489)
(433, 37666, 48928105)
(1, 233, 610)
(2, 5741, 33461)
(5, 43261, 646018)
(5, 96557, 1441889)
(13, 51641, 2012674)

问题描述 #

目前代码无法按从小到大的顺序生成马尔可夫数：比如610是序列的第11个元素，但代码会先生成远大于610的数值，当输入n=11时函数返回值为2897，不符合预期。请问有什么方案可以实现有序生成马尔可夫数序列？

解决方案 #

当前代码的核心问题是深度优先的树遍历策略会优先递归展开较早生成的三元组分支，导致大量大数值提前被生成，漏掉了更小的、存在于更深层左侧分支的数值（比如610就在第31个生成的三元组里）。要实现有序生成，可采用「最小堆优先遍历」方案替代原有链式递归逻辑：

1. 用最小堆（优先队列）存储待生成的三元组，排序依据为三元组的最大值（马尔可夫三元组的整体数值大小和最大值正相关）
2. 每次从堆中取出最小的三元组，提取其中的新数值
3. 把当前三元组衍生的两个新三元组去重后推入堆中
4. 重复上述步骤直到收集到足够的马尔可夫数

改进后代码示例 #

import heapq

def get_next_triples(triple):
    a,b,c = sorted(triple)
    # 固定两个值求第三个马尔可夫数的递推公式，比循环遍历高效
    t1 = tuple(sorted((a, b, 3*a*b - c)))
    t2 = tuple(sorted((a, c, 3*a*c - b)))
    t3 = tuple(sorted((b, c, 3*b*c - a)))
    # 排除和原三元组重复的分支，返回两个新衍生三元组
    return [t for t in [t1,t2,t3] if t != tuple(sorted(triple))]

def gen_ordered_markov():
    seen_triples = set()
    heap = []
    init_triple = tuple(sorted((1,2,5)))
    heapq.heappush(heap, (max(init_triple), init_triple))
    seen_triples.add(init_triple)
    seen_nums = {1,2,5}
    # 先按序返回前三个初始值
    yield 1
    yield 2
    yield 5
    while True:
        _, current = heapq.heappop(heap)
        for num in current:
            if num not in seen_nums:
                seen_nums.add(num)
                yield num
        # 生成衍生三元组推入堆
        for t in get_next_triples(current):
            if t not in seen_triples:
                seen_triples.add(t)
                heapq.heappush(heap, (max(t), t))

def markov(n):
    g = gen_ordered_markov()
    res = None
    for _ in range(n+1):
        res = next(g)
    print(res)

n = int(input('Enter n: '))
markov(n)

代码说明 #

• 用马尔可夫数递推公式替代循环查找新三元组，性能提升明显
• 最小堆保证每次优先处理数值最小的三元组，因此返回的数值自然按升序排列
• 额外增加了三元组去重逻辑，避免同一个三元组被重复处理

内容的提问来源于stack exchange，提问作者Sterling