python - 斐波那契调用图中的值分区(调用图是二叉树)

Question

我有一个正在进行的研究斐波那契数列的项目，这只是一个个人项目，我创建了一个二进制文件 tree class这构成了斐波那契调用图的二叉树，因此对于 f(3)我生成树:

我想为我的 tree class 创建一个方法get_partitions()遍历树以生成 root value 的分区，我在这里将顺序不同的加法视为不同部分；所以这里的例子是 f(3) , get_partitions()方法将遍历树并产生:

Partion 1: 2,1
Partion 2: 2,1,0
Partion 3: 1,1,1
Partion 4: 1,1,1,0
Partion 5: 1,0,1,1
Partion 6: 1,0,1,1,0

因为最终我想枚举斐波那契数列的每个排列，这些排列划分了 root value , 在这种情况下 3 , 所以对于 Partition 1枚举将是 (2,1),(1,2) , 或 Partion 2将被枚举 (2,1,0),(2,0,1),(1,2,0),(1,0,2),(0,2,1),(0,1,2)等等……

[编辑 1] 我关心的是 Partion 4和 Partion 5在此示例中，枚举这些部分的所有组合将产生重复部分。

给定 root value 的组合数量是否正确？会产生一个加泰罗尼亚数字吗？

我的 Tree class是:

class FibTree(object):
"""Class which builds binary tree from Fibonacci function call graph"""
def __init__(self, n, parent=None, level=None, i=None):
    if level is None:
        level = 0
    if i is None:
        i = 1
    self.n = n
    self.parent = parent
    self.level = level
    self.i = i # Node index value
    if n < 2:
        self.left = None
        self.right = None
        self.value = n
    else:
        self.left = FibTree(n - 1, self, level + 1, i*2)
        self.right = FibTree(n - 2, self, level + 1, (i*2)+1)
        self.value = self.left.value + self.right.value

对于生成树类方法的任何帮助以及对我的问题的数学启发，我将不胜感激。

[编辑:] 我如何得到我的部分 所有部分的总和必须为 Root值(value):
Partion 1:取自 1 级 (2,1)
Partion 2:使用 left child node root 的值, 但现在取 right child node 的子项的值的 root节点 (1,0) , 给出 (2,1,0) 的一部分
Partion 3:作为right child node的遍历的 root节点已经耗尽，遍历到left child node的下一层root 的值(级别 2)，并将这些子节点值用作分区的第一部分 (1,1)然后乘right child node root 的值(value)节点 (1)，给出 (1,1,1) 的一部分
Partion 4:保留前一个分区的初始分区值 (1,1) , 但与 Partion 2 一样取 right child node 的子项的值的 root节点 (1,0) , 给出 (1,1,1,0) 的一部分
Partion 5:因为根的左 child 的左 child 有 child ，所以使用这些作为分区的第一部分 (1,0)然后取 root 的左 child 的右 child 值(1)、到目前为止的部分(1,0,1) , 然后取根的右子节点 (1) , 最后一部分 (1,0,1,1)
Partion 6:作为第 5 部分，取第 5 部分的第一部分 (1,0,1) ，则Part2和Part4分别取根的右节点的子节点的值。

Answer 1

这是一个生成器，可以生成您想要的那种值，但我没有尝试找到完全优化的解决方案，因为您的问题有些地方有点困惑。

1. 您确定要包含 0 吗？它不是完全任意的，因为分区中零的最大数量是 1 的数量(例如 [1, 0, 1, 0, 1, 0])，但它们似乎没有添加任何东西。

2. 您是如何对分区进行排序的？当 n=3 并忽略零时，它们似乎按长度排序，但如果 n=8，例如，[2, 2, 2, 2] 是在 [1, 2, 2, 3] 之前还是之后？

3. 你真的想要一个类来做这件事，还是你只是用它作为例子，因为它似乎是最简单的方法？

此代码将产生斐波那契数列中值的所有排列，这些排列添加到 n 中，包括 n 本身。它仅在 n 实际上在序列中时才有效(例如 fibs(4) 将引发异常)。

代码如下:

def fibs(n, _pairs=None):
    'Return partitions in the fibonacci sequence'
    if _pairs is None:
        # Generate a dict of fib numbers, values are the previous two numbers
        # E.g. {..., 8: [3, 5], 13: [5, 8], ... n: [fib_n-2, fib_n-1]} 
        a, b, c = 0, 1, 1
        _pairs = {1: [0, 1]}
        while c < n:
            a, b = b, a + b
            c = a + b
            _pairs[c] = [a, b]

    # Yield every sum combination of pairs
    yield (n,)
    if n == 1:
        yield (1, 0)
    else:
        right, left = _pairs[n]
        for vl in fibs(left, _pairs):
            for vr in fibs(right, _pairs):
                yield vl + vr

您可以使用 set(tuple(sorted(i)) for i in fibs(n)) 轻松过滤掉重复项，并使用 itertools.permutations 创建排列。