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.
All Possible Combination of a Tree
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?
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?
Author
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.
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.
Author
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.
Why don't you just use the recursive approach? It is very simple. Here is the rough psuedocode.
There are roughly (branching factor)^depth possible trees.
exploreTree(Node)
for each child
if(child != leaf)
exploreTree(child)
else
verifyTree(child)
There are roughly (branching factor)^depth possible trees.
Author
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.
Sorry, I misunderstood what you where asking for. I thought you wanted all paths through the tree.
This should do:
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.
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
