I have a __max_depth and a __max_splits parameters, and I'd like to generate a random tree such that for each "node" I can perform a certain operation (such as generating a random number, for instance).
However, I'm pretty much stuck because I cannot understand which goes first in the nested loops: the for depth in range(0, __max_depth) or the for split in range(0, __max_splits)?
What I have in mind is basically a path that can fully traverse a tree like this (in this case, the depth is 3 and the split is 2):
- root -> node 1a -> node 2aa -> node 3aaa
-> node 3aab
-> node 2ab -> node 3aba
-> node 3abb
-> node 1b -> node 2ba -> node 3bba
-> node 3bab
-> node 2bb -> node 3bba
-> node 3bbb
I would like also to be able to understand where I am in the tree, and more specifically how deep I am in the tree (because for a depth % 2 == 0 I'd like to do certain operations, for a depth % 2 == 1 others).
Any suggestions on how to implement it in pure Python? I'm quite lost.
Edit: What I'm trying to do is generating a random walk. I'd like to traverse a nearly-infinite directed network (graph) starting from a custom point (my root), and saving all the information of the nodes I analyse given the path. The size of the area covered by the random walk is determined by the two parameters (the height of the area by max_depth, its width by max_split).
To me it's not entirely clear what you're trying to achieve, but it sounds as you're doing some kind of homework or exercise. So I will not give you program code. But a concept how to implement it yourself.
One - easy - way is to use recursion. Define a function that generates a node. This node is nothing more than a list of items - either leaves or nested nodes.
If you invoke this function pass two arguments to this function: First the intended depth of the tree, second the number of leaves, branches or "splits" a node should have.
The function should contain code that creates a list. If - and only if - the depth of the tree is zero, return a list full of random numbers. You can use the random module to achieve that. But if the desired depth is greater than zero, fill this list not with numbers but with nodes! To get nodes invoke your function again from within that function as this function is generating nodes. (This is called "recursion".) But invoke this function with a depth minus one: This way every function call will lead to more function calls (with a reduced depth). This way you will automatically generate nodes as desired, while you descend through the tree.
You might want to understand recursion first in more detail before you start your implementation. Please read more about that first, I've the feeling there is a ton of material about that online.
And - for the records - I think you will need about pretty much ten lines of code for that in the end.
EDIT: I still don't understand perfectly what you're trying to do, but consider this as a starting point:
def walk(treeNode, maxDepth, maxSpread, currentPath = "", cache = None):
if cache is None:
cache = {}
for i in range(maxSpread):
leaf = treeNode.getLeaf(i)
# do something with leaf, generate /value/
cache[currentPath] = value
if maxDepth >= 1:
walk(leaf, maxDepth - 1, maxSpread, path + "|" + str(i), cache)
Here cache stores some values you want to keep track of. The method proceeds through your tree-like network. If you want to randomize it you need to pick the nodes in a random fashion, not one by one as in my example.