Partions of values ​​in un grafo call di Fibonacci (il grafo delle chiamate è un albero binario)

Question

Ho un progetto in corso che indaga la sequenza di Fibonacci, questo è solo un progetto personale, ho creato un binario tree class che rende un albero binario del Fibonacci chiamare grafico, quindi per f(3) genero l'albero:

voglio creare un metodo di mia tree classget_partitions() che attraversa l'albero di generare partizioni del root value, ritengo qui addendi che si differenziano in ordine come diverse parti ons; così per l'esempio qui di f(3), il metodo get_partitions() avrebbe attraversare l'albero e la resa:

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 

Mentre in ultima analisi, voglio elencare ogni permutazione dei numeri di Fibonacci che partizionare il root value, in questo caso 3, quindi per Partition 1 enumerato sarebbe (2,1),(1,2), o Partion 2 sarebbe enumerato (2,1,0),(2,0,1),(1,2,0),(1,0,2),(0,2,1),(0,1,2), ecc ...

[Modifica 1] la mia preoccupazione è con Partion 4 e Partion 5 in questo esempi come enumerare tutte le combinazioni di queste partions produrrebbe duplicati partions.

Sarebbe corretto che il numero di combinazioni per un dato root value darebbe un numero di catalano?

mio 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 

sarei grato di qualsiasi aiuto per la produzione del metodo di classe albero e qualsiasi chiarimento sulla matematica al mio problema.

[EDIT:] Come ottengo i miei partions Tutti partions devono sommare a Root valore:
Partion 1: Tratto da livello 1 (2,1)
Partion 2: Utilizzare il valore left child node di root, ma ora prendere i valori dei bambini della right child node del root nodo (1,0), che invia un Partion di (2,1,0)
Partion 3: Come attraversamento right child node del nodo root è stato esaurito, traslazione al successivo livello di left child node valu e di root (livello 2), e utilizzare i questi valori di nodi figlio come prima parte partion (1,1) poi prendere il valore right child node del nodo root (1), che invia un partion di (1,1,1)
Partion 4: Mantenendo i valori partion iniziali dalla precedente partion (1,1), ma come con Partion 2 prendono i valori dei figli del right child node del root nodo (1,0), per dare un partion di (1,1,1,0)
Partion 5: come il figlio sinistro, del figlio sinistro della radice, ha figli, usano questi come prima parte della partion (1,0) quindi prendi il giusto valore figlio del figlio sinistro dello root (1), giv ing una partizione finora di (1,0,1), poi prendere il nodo figlio destro della radice (1), che invia un partion finale (1,0,1,1)
Partion 6: Come Partion 5, prendere la prima parte Partion 5 (1,0,1), poi come Partion 2 e 4 prendere la valore dei nodi figli del nodo destro della radice.

Answer 1

Ecco un generatore che produce il tipo di valori desiderato, ma non ho provato a trovare una soluzione completamente ottimizzata poiché la tua domanda è un po 'confusa in alcuni punti.

1. Sei sicuro di includere 0? Non è completamente arbitrario perché il numero massimo di zeri in una partizione è il numero di quelli (ad es. [1, 0, 1, 0, 1, 0]), ma sembra che non aggiungano nulla.

2. Come si ordinano esattamente le partizioni? Quando n = 3 e ignorando gli zeri, sembrano essere ordinati per lunghezza, ma se n = 8, ad esempio, è [2, 2, 2] prima o dopo [1, 2, 2, 3]?

3. Realmente vuoi che una classe lo faccia, o l'hai semplicemente usato come esempio perché sembrava il modo più semplice?

Questo codice produrrà tutte le permutazioni di valori nella sequenza Fibonacci che si aggiungono alla n, compreso n stessa. Funzionerà solo se n è effettivamente nella sequenza (ad esempio fibs(4) genererà un'eccezione).

Ecco il codice:

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 

Si può facilmente filtrare i duplicati utilizzando set(tuple(sorted(i)) for i in fibs(n)) e creare permutazioni usando itertools.permutations.