用python生成马尔可夫数序列

Question

我想做一些事情来更好地理解收益和收益。目标是按顺序生成马尔可夫序列，第一个元素是索引0。https://en.wikipedia.org/wiki/Markov_number

我想出了以下代码。

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.关于如何按顺序生成序列有什么建议吗？

Answer 1

这是我对这个问题的贡献(不是答案)，我完全重新编辑了我的第一次尝试，我不会再继续下去了。为什么？问题不是定义良好的

1. 你推荐作为参考的维基百科文章很糟糕(参见我的评论)
2. 你没有指定排序规则和马尔可夫数的定义我自己也用技术/研究论文记录了，但还没有找到任何东西(甚至没有对马尔可夫数的正确定义！)

所以，只要你不改进这个问题，让每个人都能访问它，我就会认为它是接近的。

建议

向社区询问如何为/yield from实现生成有序马尔可夫，您应该有一个有效的示例并了解它(？)，即在这种情况下选择另一个(更简单的)问题来开始了解problem的更多信息

Consideration

• 马尔可夫数是二叉树的节点，因此实现二叉树

• 树的每一层都有两个(相对)最小的、最外面的叶子，它们由斐波那契和佩尔序列描述。斐波纳契数是最小的。它们可以用作包含n-马尔可夫数

的列表大小的中断条件

• 通过保持简单，使用贪婪算法...例如，如果您想要一个n阶马尔可夫数列表，请考虑一个完美二叉树(它的计算成本很高，大小由初始值为1、公共比为2的几何序列建模)，并按递增顺序对它们进行排序，并考虑此类列表的前n个条目，smt如下所示

list(sorted(markov_triples, key=lambda p: p[1]))[:n]

Danger正如在评论中提到的，在维基百科的文章中，对应于马尔可夫数194的节点没有正确标记，请参阅我的评论以供参考。这里有一个比维基百科更详细的Markov tree。

关于树叶计算的示例代码。我使用一棵完美的树作为参考，它的节点可以唯一地描述为一个几何序列，用来定位叶子，然后找到通向根的左右路径序列，最后应用“马尔可夫规则”来找到三元组：

from math import log

def find_lv(n): # provided that the root as vertex 1, n: absolute node index
    return int(log(n, 2))

def branch_path(n, k): # leaf to root
    # n: depth, k: 0 <= index <= 2**n - 1
    path = [k]
    for i in range(n-1):
        if path[-1] % 2 == 0:
            path += [path[-1] // 2]
        else:
            path += [path[-1] // 2]
    return path

def branch_path_as_directions(path): # leaf to root
    return ['L' if p % 2 == 0 else 'R' for p in path[:-1]] # the root should be skiped!

def new_sol(triple):
    x, y, z = triple
    return (x, y, 3*x*y - z)

def left_triple(triple): 
    x, y, z = triple
    return (x, z, y)

def right_triple(triple): 
    x, y, z = triple
    return (y, z, x)

def markov_triples(n):
   # n: is the absolute position of a node in the tree, i.e. wrt to a geometric series
   # return the branch of triples corresponding to that node
    # initial values of the sequence
    triples = [(1, 1, 1), (1, 1, 2), (1, 2, 5)]
    if n == -2:
        return triples[0]
    if n == -1:
        return triples[1]
    if n == 0:
        return triples[2]

    depth = find_lv(n) + 1

    # get path the leaf with n
    path = branch_path(depth, n)
    path_l_r = branch_path_as_directions(path)
        
    # flow from root to leaf
    for direction in path_l_r[::-1]:
        if direction == 'L':
            triples += [new_sol(left_triple(triples[-1]))]
        else:
            triples += [new_sol(right_triple(triples[-1]))]
            
    return triples

print(markov_triples(10))

输出

[(1, 2, 5), (1, 5, 13), (5, 13, 194), (5, 194, 2897)]

Answer 2

更新。我能够使用队列找到一个合理更好的解决方案(尽管不是很完美)。

# Markov Numbers

seed = (1,2,5)
markov = set()
markov.add(1)
queue = []
queue.append(seed)

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

while len(markov) <= n**3:
    curr = queue.pop()
    p,q,r = (curr)
    markov.add(p)
    markov.add(q)
    markov.add(r)
    left = (p,r,3*p*r-q)
    right = (q,r,3*q*r-p)
    queue.insert(0,left)
    queue.insert(0,right)
markov = list(markov)
markov.sort()
print(markov[n])

我一直测试到n=39 (从索引0开始)。这与OEIS中的前40个元素相匹配。https://oeis.org/A002559/list

0th element: 1
1th element: 2
2th element: 5
3th element: 13
4th element: 29
5th element: 34
6th element: 89
7th element: 169
8th element: 194
9th element: 233
10th element: 433
11th element: 610
12th element: 985
13th element: 1325
14th element: 1597
15th element: 2897
16th element: 4181
17th element: 5741
18th element: 6466
19th element: 7561
20th element: 9077
21th element: 10946
22th element: 14701
23th element: 28657
24th element: 33461
25th element: 37666
26th element: 43261
27th element: 51641
28th element: 62210
29th element: 75025
30th element: 96557
31th element: 135137
32th element: 195025
33th element: 196418
34th element: 294685
35th element: 426389
36th element: 499393
37th element: 514229
38th element: 646018
39th element: 925765

这并不完美，因为它仍然需要比n更远的搜索才能得到关于n>10的准确结果，这就是为什么有n**3项的原因。如果有人能解释一个更好的方法，我将不胜感激。