Recursion along each path in the tree
I am stuck on a tree-involvement programming question for a project. The problem itself is just a sub-problem of the larger question (but I won't post it here as it's not very relevant). Any problem:
I am trying to traverse each path in the tree and calculate the associated value.
Situation, for example, as in this tree:
a
b b
Now the result I should get multiplication like this:
leave1 = a * b
leave2 = a * (1-b)
leave3 = (1-a) * b
leave4 = (1-a) * (1-b)
And so the leaves one level down in the tree will basically be the result (note that they don't really exist, its just conceptual).
Now I want to do it recursively, but there are several problems: The values for a and b are generated during the traversal, but the value for b, for example, should only be generated 1 time. All values are 0 or 1. If you take the left child of node A, you are using the value of A in the multiplication. in the right way you are using 1-A value.
Moreover, the tree is always perfect, that is, complete and balanced.
Now I have (I am programming in python, but the more the algorithm is generally interested in this question):
def f(n):
if n == 1:
return [1]
generate value #(a, b or whatever one it is)
g = f(n/2)
h = scalarmultiply(value,g)
return h.append(g - h)
Note that g and h are lists. This code was given by one of my professors as possible help, but I don't think it does what I want. At least it won't give me a list h as a result, which has a result for each path. In particular, I don't think it distinguishes between b
and 1-b
. I see it wrong and how do I do it?
I am not very good at programming, so try to explain if you can :-)
source to share
Try something like this:
def f(element_count):
if element_count == 1: #<-------------------------------A
return [1,] #at the root node - it has to be 1 otherwise this is pointless
current_value = get_the_value_however_you_need_to()#<----B
result_so_far = f(element_count/2) #<-------------------C
result = []
for i in result_so_far:#<--------------------------------D
result.append(i*current_value)
result.append(i*(1-current_value))
result.append((1-i)*current_value)
result.append((1-i)*(1-current_value))
return result
This is how it works:
Say that you wanted to work with a three-layer pyramid. Then element_count will be the number of elements in the third layer for you to call f(4)
. The at condition of A fails, so we continue with B where the next value is generated. Now in C let's call f(2)
.
Process in is f(2)
similar, f(2)
calls f(1)
and f(1)
returns [1,]
in f(2)
. Now we start going back to the widest part of the tree ...
I'm not sure where your lecturer ended up with the function ending. The for loop points to the multiplication you explain and creates a list that is then returned
source to share
If I understand correctly, you want to create a binary tree like this:
A
/ \
/ \
/ \
B C
/ \ / \
D E F G
If the logical values ( 1
, 0
or Python equivalents True
and False
) lower-level units are calculated from the values of their parents and grandparents, using the following rules:
D = A and B
E = A and not B
F = not A and C
G = not A and not C
That is, each node's right children compute their values based on this inverse. Next, you indicated that the tree is defined by one root value ( a
) and another value that is used for both root children ( b
).
Here's a function that will compute the value of any node of such a tree. Tree positions are defined by integer index in the same way as a binary heap, with the parent node N
having N//2
and the children having 2*N
and 2*N+1
(with the root node 1
). It uses a dictionary of notes to repeat the same values over and over.
def tree_value(n, a, b, memo=None):
if memo is None:
memo = {1:a, 2:b, 3:b} # this initialization covers our base cases
if n not in memo: # if our value is unknown, compute it
parent, parent_dir = divmod(n, 2)
parent_val = tree_value(parent, a, b, memo) # recurse
grandparent, grandparent_dir = divmod(parent, 2)
grandparent_val = tree_value(grandparent, a, b, memo) # recurse again
if parent_dir: # we're a right child, so invert our parent value
parent_val = not parent_val
if grandparent_dir: # our parent is grandparent right child, so invert
grandparent_val = not grandparent_val
memo[n] = parent_val and grandparent_val
return memo[n]
You might probably improve performance a little by noticing that the grandparent value will always be in the memo dict after the parent value has been calculated, but I left that so the code is clearer.
If you need to efficiently compute many values from the same tree (not just one), you probably want to store a persistent annotation dictionary somewhere, perhaps as a value in a global dict, using a tuple (a, b)
.
source to share