Public Group

# 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.

## 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 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?

##### 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 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 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 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 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 on other sites
Sorry, I misunderstood what you where asking for. I thought you wanted all paths through the tree.

##### 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 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.

1. 1
2. 2
Rutin
23
3. 3
4. 4
JoeJ
18
5. 5

• 14
• 23
• 11
• 11
• 9
• ### Forum Statistics

• Total Topics
631766
• Total Posts
3002233
×