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.
Here's an generator which produces the sort of values you want, but I haven't tried to find a fully optimised solution since your question is a bit confusing in places.
Are you sure about including 0? Its not completely arbitrary because the maximum number of zeros in a partition is the number of ones (e.g. [1, 0, 1, 0, 1, 0]), but they don't seem to add anything.
How exactly do you order the partitions? When n=3, and ignoring zeros, they appear to be ordered by length, but if n=8, for example, is [2, 2, 2, 2] before or after [1, 2, 2, 3]?
Do you actually want a class to do this, or did you just use that as an example because it seemed the easiest way?
This code will yield all permutations of values in the fibonacci sequence which add to n
, including n
itself. It will only work if n
is actually in the sequence (e.g. fibs(4)
will raise an exception).
Here's the code:
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
You can easily filter out duplicates using set(tuple(sorted(i)) for i in fibs(n))
and create permutations using itertools.permutations
.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With