Jump to content
  • Advertisement
Sign in to follow this  
Concentrate

All Possible Combination of a Tree

This topic is 2711 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I have a general tree, which can hold any number of children, does not necessarily have to be binary. And I need to create all possible binary combination of that tree. Any help on ideas or something.


Share this post


Link to post
Share on other sites
Advertisement
Generating complete lists for "all possible combination" problems will suffer from combinatorial explosion even for small numbers of items.

While you can often loop over the set of data for all permutations, attempting to create instances of everything can quickly require amazing amounts of storage.

What is the real problem you are trying to solve?

Share this post


Link to post
Share on other sites

Generating complete lists for "all possible combination" problems will suffer from combinatorial explosion even for small numbers of items.

While you can often loop over the set of data for all permutations, attempting to create instances of everything can quickly require amazing amounts of storage.

What is the real problem you are trying to solve?


The problem needs to loop through all necessarily binary combinations of the tree for 100% correctness. I will of course have a parameter to specify the depth. I just need some idea on how to generate such
combination of trees.

Share this post


Link to post
Share on other sites
Why does it need to look at every permutation for 100% correctness? That sounds like a brute force approach - there should be a better algorithm for this job, or at least a heuristic to make it reasonable in the average case.

Share this post


Link to post
Share on other sites

Why does it need to look at every permutation for 100% correctness? That sounds like a brute force approach - there should be a better algorithm for this job, or at least a heuristic to make it reasonable in the average case.


Thats true. Right now I talked with my professor, and he doesn't have any heuristic approach to the problem. He wants me to first try brute force. And if it produces correct results, then we will take a heuristic approach else possible go with statistical inference. As of right now, I have something like this to generate all possible combination, not completely sure if its correct, mind checking it.


std::vector<NewickTreeElement> createAllPossibleBinaryTree(const NewickTreeElement& mainRoot, const int DEPTH = 1){
std::vector<NewickTreeElement> trees;

//add the main tree itself then all possible combination of it
trees.push_back( mainRoot );

for(int depth = 0; depth < DEPTH; ++depth){
NewickTreeElement root = trees[depth];
const size_t numberOfChildrens = root.getChildrens().size();
//check if already binary
if(numberOfChildrens <= 2) continue;

for(size_t i = 0; i < numberOfChildrens; ++i){
for(size_t j = i + 1; j < numberOfChildrens ; ++j){
//combine two subtree into one subtree
NewickTreeElement combinedPair;
combinedPair.addChild( root.getChildrens() );
combinedPair.addChild( root.getChildrens()[j] );

NewickTreeElement tree;
tree.addChild( combinedPair );

for(size_t k = 0; k < numberOfChildrens; ++k){
if(k == i || k == j) continue; //skip the combined childs
tree.addChild( root.getChildrens()[k] ); //and just add all the other childs
}
trees.push_back( tree );
}
}
}

return trees;
}


Basically, it takes two children combines it into and, and copies all the other children in the tree except the 2 picked child, and create a new tree. It does this for all possible 2 pair child. Then it repeats this on the
all newly created tree for DEPTH amount of times. Does anyone now how many combinations there should be? Maybe something like 2^n - n, where n is number of children.

Share this post


Link to post
Share on other sites
Why don't you just use the recursive approach? It is very simple. Here is the rough psuedocode.

exploreTree(Node)
for each child
if(child != leaf)
exploreTree(child)
else
verifyTree(child)

There are roughly (branching factor)^depth possible trees.

Share this post


Link to post
Share on other sites

Why don't you just use the recursive approach? It is very simple. Here is the rough psuedocode.

exploreTree(Node)
for each child
if(child != leaf)
exploreTree(child)
else
verifyTree(child)

There are roughly (branching factor)^depth possible trees.


I don't get how DFS produces all possible combinations.


Share this post


Link to post
Share on other sites
This should do:

ContainerOfTrees generate_all_binary_trees(size) {
if (size == 0)
return contrainer_of_trees_with_only_an_empty_tree;

ContainerOfTrees result;

for (int i=0; i<size; ++i) {
ContainerOfTrees left_trees = generate_all_binary_trees(i);
ContainerOfTrees right_trees = generate_all_binary_trees(size-i-1);
for (Tree left in left_trees) {
for (Tree right in right_trees) {
result.push(build_tree(left, right));
}
}
}

return result;
}

EDIT: Something is broken with the indentation inside code tags...

If you just want to count the number of trees, there are much better methods.

Share this post


Link to post
Share on other sites

Does anyone now how many combinations there should be? Maybe something like 2^n - n, where n is number of children.

Oh, it's worse than that. For binary trees of depth exactly n, the recurrence is f(n)=f(n-1)^2+2f(n-1), n(1)=1. That comes out to 2+(2^(n-1))-1. That's, for instance, 65 thousand trees for depth 5.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!