I have an ongoing project investigating the Fibonacci sequence, this is just a personal project, I have created a binary tree class
which makes a binary tree of the Fibonacci call graph, so for f(3)
I generate the tree:
I want to create a method of my tree class
get_partitions()
that traverses the tree to generate partitions of the root value
, I regard here summands that differ in order as different partions; so for the example here of f(3)
, the get_partitions()
method would traverse the tree and yield:
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
As ultimately I want to enumerate every permutation of Fibonacci numbers that Partition the root value
, in this case 3
, so for Partition 1
enumerated would be (2,1),(1,2)
, or Partion 2
would be enumerated (2,1,0),(2,0,1),(1,2,0),(1,0,2),(0,2,1),(0,1,2)
, etc…
[Edit 1] My concern is with Partion 4
and Partion 5
in this examples as enumerating all combinations of these partions would yield duplicate partions.
Would it be correct that the number of combinations for a given root value
would yield a Catalan number?
My Tree class
is:
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
I'd be grateful of any help for producing the tree class method and any enlightenment on the maths to my problem.
[EDIT:] How I get my partions
All partions must sum to Root
value:
Partion 1:
Taken from Level 1 (2,1)
Partion 2:
Use the left child node
value of root
, but now take the values of the children of the right child node
of the root
node (1,0)
, to give a Partion of (2,1,0)
Partion 3:
As traversal of right child node
of the root
node has been exhausted, traverse to next level of left child node
value of root
(level 2), and use the these child node values as first part of partion (1,1)
then take the right child node
value of the root
node (1), to give a partion of (1,1,1)
Partion 4:
Keeping the initial partion values from the previous partion (1,1)
, but as with Partion 2
take the values of the children of the right child node
of the root
node (1,0)
, to give a Partion of (1,1,1,0)
Partion 5:
As the left child, of the left child of the root, has children, use these as the first part of the partion (1,0)
then take the right child value of the left child of the root
(1), giving a partion so far of (1,0,1)
, then take the right child node of the root (1)
, to give a final partion of (1,0,1,1)
Partion 6:
As Partion 5, take the first part of Partion 5 (1,0,1)
, then as Partion 2 and 4 take the value of the child nodes of the right node of the root.
1
nodes have a1
and0
child? It seems like the recursion should terminate there. If not, one could make a case that you can have arbitrarily many0
children, since they don't actually contribute anything.1
nodes do have a1
and0
child, but as you say it may be the arbitrary0
children will ultimately prove to be no use to me as they have no magnitude, so I may need to filter them out in some way.