Разделы значений в графе вызовов Фибоначчи (граф вызовов - это двоичное дерево) - PullRequest
Новая
       18

Разделы значений в графе вызовов Фибоначчи (граф вызовов - это двоичное дерево)

9 голосов
/ 11 марта 2012

У меня есть текущий проект по исследованию последовательности Фибоначчи, это всего лишь личный проект, я создал двоичный файл tree class, который создает двоичное дерево графа вызовов Фибоначчи, поэтому для f(3) я генерирую дерево:

Binary Tree

Я хочу создать метод моего 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 значение:
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 (1), чтобы получить разделение (1,1,1)
Partion 4: Сохранение начальных значений разбиенияиз предыдущего раздела (1,1), но, как и в случае Partion 2, возьмите значения дочерних элементов right child node узла root (1,0), чтобы получить долю в (1,1,1,0)
Partion 5: каку левого потомка левого потомка корня есть дети, используйте их в качестве первой части части (1,0), затем примите значение правого дочернего элемента левого потомка root (1), давая таким образомвдали от (1,0,1), затем возьмите правый дочерний узел корня (1), чтобы получить конечный раздел (1,0,1,1)
Partion 6:. В качестве раздела 5 выберите первую часть раздела 5 (1,0,1), затемв качестве Разделов 2 и 4 берут значение дочерних узлов правого узла корня.

1 Ответ

1 голос
/ 11 марта 2012

Вот генератор, который выдает нужные вам значения, но я не пытался найти полностью оптимизированное решение, поскольку ваш вопрос местами сбивает с толку.

  1. Вы уверены, что включили 0? Это не совсем произвольно, потому что максимальное количество нулей в разделе - это число единиц (например, [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.

...