Sign in to follow this  

All Possible Combination of a Tree

This topic is 2492 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
Generating complete lists for "all possible combination" problems will suffer from [url="http://en.wikipedia.org/wiki/Combinatorial_explosion"]combinatorial explosion[/url] 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
[quote name='frob' timestamp='1297876373' post='4775020']
Generating complete lists for "all possible combination" problems will suffer from [url="http://en.wikipedia.org/wiki/Combinatorial_explosion"]combinatorial explosion[/url] 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?
[/quote]

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
[quote name='rip-off' timestamp='1297877620' post='4775029']
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.
[/quote]

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.
[code]

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()[i] );
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;
}
[/code]

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.
[code]
exploreTree(Node)
for each child
if(child != leaf)
exploreTree(child)
else
verifyTree(child)
[/code]
There are roughly (branching factor)^depth possible trees.

Share this post


Link to post
Share on other sites
[quote name='EricTheRed' timestamp='1297878913' post='4775038']
Why don't you just use the recursive approach? It is very simple. Here is the rough psuedocode.
[code]
exploreTree(Node)
for each child
if(child != leaf)
exploreTree(child)
else
verifyTree(child)
[/code]
There are roughly (branching factor)^depth possible trees.
[/quote]

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


Share this post


Link to post
Share on other sites
This should do:

[code]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;
}
[/code]
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
[quote name='D.Chhetri' timestamp='1297878270' post='4775032']
Does anyone now how many combinations there should be? Maybe something like 2^n - n, where n is number of children.
[/quote]
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
[quote name='Sneftel' timestamp='1297886897' post='4775094']
[quote name='D.Chhetri' timestamp='1297878270' post='4775032']
Does anyone now how many combinations there should be? Maybe something like 2^n - n, where n is number of children.
[/quote]
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.
[/quote]

Maybe I'm missing something how is plugging 5 for n into the formula 2^(n-1) + 1 equals 65k?

Share this post


Link to post
Share on other sites
[quote name='D.Chhetri' timestamp='1297900220' post='4775170']
[quote name='Sneftel' timestamp='1297886897' post='4775094']
[quote name='D.Chhetri' timestamp='1297878270' post='4775032']
Does anyone now how many combinations there should be? Maybe something like 2^n - n, where n is number of children.
[/quote]
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.
[/quote]

Maybe I'm missing something how is plugging 5 for n into the formula 2^(n-1) + 1 equals 65k?
[/quote]
Whoops, typo. The equation is 2[b]^[/b](2^(n-1))-1. Double exponentiation.

Share this post


Link to post
Share on other sites
[quote name='D.Chhetri' timestamp='1297896731' post='4775160']
Oh I see. Thanks. I need the actual combination, not the number. Alvaro, I will give your algorithm a shot. Have you done this before with that algorithm?
[/quote]

No, but I am good at this type of thing. :)

Share this post


Link to post
Share on other sites
Hey alvaro, just a quick question on your algorithm. Is this what you mean :

[code]
ContainerOfTrees generate_all_binary_trees(root) {
if (root.isLeaf())
return contrainer_of_trees_with_only_an_empty_tree;

ContainerOfTrees result;


size_t size = root.childrenCount();

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

return result;
}
[font="'Courier New"][size="2"][color="#666600"]
[/color][/size][/font]
[/code]

[color="#666600"]I just want to be sure.[/color]

Share this post


Link to post
Share on other sites
[quote name='Sneftel' timestamp='1297903888' post='4775196']
[quote name='D.Chhetri' timestamp='1297900220' post='4775170']
[quote name='Sneftel' timestamp='1297886897' post='4775094']
[quote name='D.Chhetri' timestamp='1297878270' post='4775032']
Does anyone now how many combinations there should be? Maybe something like 2^n - n, where n is number of children.
[/quote]
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.
[/quote]

Maybe I'm missing something how is plugging 5 for n into the formula 2^(n-1) + 1 equals 65k?
[/quote]
Whoops, typo. The equation is 2[b]^[/b](2^(n-1))-1. Double exponentiation.
[/quote]

Hey, do you have a link to the proof of this? Or some sort of reference?

Share this post


Link to post
Share on other sites
[quote name='D.Chhetri' timestamp='1297905275' post='4775206']
Hey alvaro, just a quick question on your algorithm. Is this what you mean :

[code]
ContainerOfTrees generate_all_binary_trees(root) {
if (root.isLeaf())
return contrainer_of_trees_with_only_an_empty_tree;

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

return result;
}
[font="'Courier New"][size="2"][color="#666600"]
[/color][/size][/font]
[/code]

[color="#666600"]I just want to be sure.[/color]
[/quote]

I think the pseudo-code I posted was correct. Here it is in working C++ (using boost::shared_ptr):
[code]#include <iostream>
#include <boost/smart_ptr.hpp>
#include <vector>

struct Node {
boost::shared_ptr<Node> left, right;
Node(boost::shared_ptr<Node> left, boost::shared_ptr<Node> right)
: left(left), right(right) {
}
};

typedef boost::shared_ptr<Node> Tree;

Tree make_tree(Tree left, Tree right) {
return Tree(new Node(left, right));
}

typedef std::vector<Tree> TreeVector;

std::ostream &operator<<(std::ostream &os, Tree n) {
if (n != Tree()) {
os << '(' << n->left << ')' << n->right;
}
return os;
}

TreeVector generate_trees(int nodes) {
if (nodes == 0)
return TreeVector(1);
TreeVector result;
for (int i=0; i<nodes; ++i) {
TreeVector left_trees = generate_trees(i);
TreeVector right_trees = generate_trees(nodes-i-1);
for (TreeVector::iterator i = left_trees.begin(),
end_i = left_trees.end(); i != end_i; ++i) {
for (TreeVector::iterator j = right_trees.begin(),
end_j = right_trees.end(); j != end_j; ++j) {
result.push_back(make_tree(*i, *j));
}
}
}
return result;
}

int main() {
TreeVector trees = generate_trees(10);
for (TreeVector::const_iterator i = trees.begin(),
end_i = trees.end(); i != end_i; ++i) {
std::cout << *i << '\n';
}
}
[/code]

Share this post


Link to post
Share on other sites
[quote name='D.Chhetri' timestamp='1297905780' post='4775209']
[quote name='Sneftel' timestamp='1297903888' post='4775196']
Whoops, typo. The equation is 2[b]^[/b](2^(n-1))-1. Double exponentiation.
[/quote]

Hey, do you have a link to the proof of this? Or some sort of reference?
[/quote]

A vanilla application of mathematical induction will tell you that the formula is correct.

Share this post


Link to post
Share on other sites
Oh I see. I think I might have been mistaken in my words. I was not trying to generate all possible binary tree given of N nodes size. What I was trying to do was given a general tree, make all possible binary combination of that general tree,. Which is why I posted the above modification on your algorithm. I think its the same process as your algorithm. Unless, I'm being confused somewhere.

EDIT: and sorry, I was referring more to the reoccurrence relation.

Share this post


Link to post
Share on other sites
[quote name='D.Chhetri' timestamp='1297906569' post='4775221']
Oh I see. I think I might have been mistaken in my words. I was not trying to generate all possible binary tree given of N nodes size. What I was trying to do was given a general tree, make all possible binary combination of that general tree,. Which is why I posted the above modification on your algorithm. I think its the same process as your algorithm. Unless, I'm being confused somewhere.[/quote]

I am the confused one. I still don't understand what problem you are trying to solve, so I solved one that sounds similar but I understand. :)

If you post a detailed description of what you are trying to do, I'll try to help you.

[quote]EDIT: and sorry, I was referring more to the reoccurrence relation.[/quote]
You pick a tree of depth n-1 to put on the left and a tree of depth n-1 to put on the right, or you leave the left empty and put a tree of depth n-1 on the right, or you leave the right empty and put a tree of depth n-1 on the left. The total count is:

f(n) = f(n-1)*f(n-1) + f(n-1) + f(n-1) = f(n-1)^2 + 2*f(n-1).

Share this post


Link to post
Share on other sites
[quote name='alvaro' timestamp='1297907135' post='4775225']
[quote name='D.Chhetri' timestamp='1297906569' post='4775221']
Oh I see. I think I might have been mistaken in my words. I was not trying to generate all possible binary tree given of N nodes size. What I was trying to do was given a general tree, make all possible binary combination of that general tree,. Which is why I posted the above modification on your algorithm. I think its the same process as your algorithm. Unless, I'm being confused somewhere.[/quote]

I am the confused one. I still don't understand what problem you are trying to solve, so I solved one that sounds similar but I understand. :)

If you post a detailed description of what you are trying to do, I'll try to help you.

[quote]EDIT: and sorry, I was referring more to the reoccurrence relation.[/quote]
You pick a tree of depth n-1 to put on the left and a tree of depth n-1 to put on the right, or you leave the left empty and put a tree of depth n-1 on the right, or you leave the right empty and put a tree of depth n-1 on the left. The total count is:

f(n) = f(n-1)*f(n-1) + f(n-1) + f(n-1) = f(n-1)^2 + 2*f(n-1).
[/quote]

I can't try to explain the problem in complete detail, because its too much. But the problem at hand right now is this: I have a general tree, for example :

[code]
ROOT
/ | \
c1 c2 c3
[/code]

Now I need to take the above tree, and generate all possible binary tree from it. For example , an instance could be :
[code]
ROOT
/ \
p1 c3
/ \
c1 c2
[/code]

So essentially, p1 is a 'combined' child. Another instance could be :
[code]
ROOT
/ \
c1 p3
/ \
c2 c3
[/code]

and so on. I need to create all possible binary tree's from the given general trees. At first I thought there was [i]Combination(numberOfNodes,2)[/i] of different combination, then I realized that those combinations
could it self be turned into trees. So I think there could possible be C(n,2)*C(n-2 , 2) ... C(2,2) number of combinations. But as shown its 2^( 2^(n-1) ) + 1

Share this post


Link to post
Share on other sites
The problem I solved is roughly equivalent to transforming a tree of depth 1 (like the one you just used as an example) into a binary tree in all possible ways. If you have a more complicated tree, you can still use this algorithm at any level where you find more than two branches.

You can use some form of backtracking to solve your original problem: You traverse the original tree in some order, and when you find a node with more than two descendants, you try cutting the descendants in two non-empty groups in every way possible. Since the order seems to matter, you'll have k-1 possible cuts if there are k descendants.

I can see how writing this recursive algorithm can be tricky. Good luck.

Share this post


Link to post
Share on other sites
Several of your posts state or hint that you want to actually create them all, simultaneously.

Are you including all forms of binary trees, not just those that are balanced? If so, the existing combinatorial explosion gets much, much, much worse than the above posts say.

If you limit yourself to balanced binary trees you will have bigger than factorial growth for most numbers. A full balanced tree will be exactly factorial, and incomplete balanced trees will be more than factorial because the incomplete nodes can shuffle among the bottom row. For 15 items in a fully balanced tree that's 1.3*10^12 permutations.


If you want to have all possible layouts, not just balanced binary trees, you are going to have a tremendous number of variations. Just trying to come up with a formula to express it makes my brain work up a sweat, but the number has extremely rapid growth. The growth for all possible tree layouts makes the factorial growth of balanced trees look easy.

Is it enough to simply iterate over them, or do you need to actually create every one of them? Consider that with just 10 nodes and allowing unbalanced trees you will have more variations than you can access with 32-bit memory pointers. If you need to actually process them all I cannot imagine how a brute force method will work for any non-trivial number of nodes.

Share this post


Link to post
Share on other sites

This topic is 2492 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this