Części wartości na wykresie wywołania Fibonacciego (wykres wywołania jest drzewem binarnym)

Question

Mam trwający projekt badający sekwencję Fibonacciego, to tylko osobisty projekt. Stworzyłem plik binarny tree class, który tworzy binarne drzewo Fibonacciego nazywamy wykres, więc dla f(3) I wygenerować drzewa:

Chcę utworzyć metodę mojego tree classget_partitions() który przemierza drzewo generowania partycji na root value, uważam tutaj summands, które różnią się w kolejności, inny parti ons; tak na przykład tu f(3) metoda get_partitions() będzie przechodzić przez drzewa i wydajność:

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 

Jak ostatecznie chcę wyliczać każdą permutację liczb Fibonacciego, które rozdzielają root value, w tym przypadku 3, więc dla Partition 1 wyliczone byłoby (2,1),(1,2) lub Partion 2 będzie wyliczone (2,1,0),(2,0,1),(1,2,0),(1,0,2),(0,2,1),(0,1,2), etc ...

[Edytuj 1] Moim problemem jest to, ze Partion 4 i Partion 5 w tym przykłady jak wylicza wszystkie kombinacje tych partions przyniesie duplikaty partycje.

Czy to prawda, że ​​liczba kombinacji dla danego root value przyniosłaby numer kataloński?

My Tree class jest:

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 

byłbym wdzięczny o jakąkolwiek pomoc dla produkcji metody klasy i wszelkie drzewo oświecenia na matematyce do mojego problemu.

[EDIT:] Jak mogę dostać moje partions Wszystkie partions muszą sumować się do Root wartość:
Partion 1: zaczerpnięte z poziomu 1 (2,1)
Partion 2: użyć wartości left child node od root, ale teraz przyjąć wartości dzieci z right child node węzła root(1,0), otrzymując partion z (2,1,0)
Partion 3: Ponieważ przechodzenie z right child node węzła root została wyczerpana i przechodzić do następnego etapu left child node Valu E root (poziom 2) i za pomocą tych wartości węzłów podrzędnych jak pierwsza część partion (1,1) następnie wartość right child node węzła root (1), z wytworzeniem partion z (1,1,1)
Partion 4: Utrzymywanie wartości początkowe partion Od? poprzednia partion (1,1), ale jak Partion 2 wziąć wartości dzieci z right child node węzła root(1,0), aby dać partion z (1,1,1,0)
Partion 5: w lewym dziecka, od lewej dziecka korzenia, ma dzieci, z nich korzystać jako pierwsza część partycji (1,0) następnie weź prawą wartość podrzędną lewego dziecka z root (1), giv ing partion jak dotąd (1,0,1), następnie odpowiedni węzeł dziecka korzenia (1), uzyskując końcową partion z (1,0,1,1)
Partion 6: jako partion 5, ma pierwszą część partion 5 (1,0,1), a następnie jako partion 2 i 4 wziąć wartość węzłów potomnych prawego węzła głównego.

Answer 1

Oto generator, który generuje pożądane wartości, ale nie próbowałem znaleźć w pełni zoptymalizowanego rozwiązania, ponieważ twoje pytanie jest nieco mylące w niektórych miejscach.

1. Czy jesteś pewien co do włączenia 0? Nie jest całkowicie arbitralny, ponieważ maksymalna liczba zer w partycji to liczba z nich (np. [1, 0, 1, 0, 1, 0]), ale nie wydają się niczego dodawać.

2. Jak dokładnie zamawiasz partycje? Gdy n = 3 i ignorowanie zer, wydaje się, że są uporządkowane według długości, ale jeśli n = 8, na przykład, jest [2, 2, 2, 2] przed lub po [1, 2, 2, 3]?

3. Czy rzeczywiście chcesz, aby to zrobiła klasa, czy po prostu użyłeś tego jako przykładu, ponieważ wydawało się to najprostszym sposobem?

Ten kod uzyskując wszystkie kombinacje wartości w Fibonacciego się do łatwiejszego n tym n się. Będzie działać tylko wtedy, gdy n jest rzeczywiście w sekwencji (np. fibs(4) zgłosi wyjątek).

Oto kod:

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 

Można łatwo filtrować duplikaty używając set(tuple(sorted(i)) for i in fibs(n)) i tworzą permutacje użyciu itertools.permutations.