445,820 Members | 1,142 Online
Need help? Post your question and get tips & solutions from a community of 445,820 IT Pros & Developers. It's quick & easy.

Any ideas on how to implement this? (hierarchy related)

 P: n/a Essentially what the program needs to do is split apart a large group of data and then it further splits apart the groups of data, etc... For example, Level 0 starts off with a large array data. The data is split apart into "n" groups. Then each group in there is also split apart into "n" groups and it continues on like that. For each branch of data the matrix is " Here is a quick picture I drew to illustrate what I'm doing: http://members.shaw.ca/fivelitermustang/split.gif I have all the code written for the functions and things and I can make the program do what I need to do if I hardcode it but I need to program to be able to take in any type of dimensions of data and split into any number of levels defined by the user. I have already hardcoded the split from 0->1, which is fine. I need to be able to split the resulting matrices of data into further and further levels specified by the user. To calculate the split from 1->2 I must take each of the 2 branches of that matrix and split it into two pieces... yielding 4 branches on the next level. To calculate the split from 2->3 I must take each of the 4 branches of that matrix and split that into two pieces... yielding 8 branches on the next level. I also need to find a way to iterate through each branch infinitely many levels deep. The function needs to have the data passed in from level 1 to calculate level 2. When level two is calculated the function is called again with the blocks from level 2 to generate blocks in level 3. I am not sure how to do this... for example if the user wanted to split the data into 3 groups then the function to stem 3 more branches off each block would be used 3 times on the first level, then it would have to be used 9 times on the second level and then 27 times on the third level... etc... How would I mathematically implement that? In addition what would be a good way to store the data in each "block"... I'm thinking a three dimensional array where the first dimension is an index number and the last two dimensions store the actual information in that matrix. Jul 22 '05 #1
4 Replies

 P: n/a In comp.lang.c++ "fivelitermustang" wrote: Essentially what the program needs to do is split apart a large group ofdata and then it further splits apart the groups of data, etc...For example, Level 0 starts off with a large array data. The data is splitapart into "n" groups. Then each group in there is also split apart into"n" groups and it continues on like that. For each branch of data thematrix is "Here is a quick picture I drew to illustrate what I'm doing:http://members.shaw.ca/fivelitermustang/split.gif That is a binary tree. Most solutions involve recursion. There should be source code all over the net for them. Jul 22 '05 #2

 P: n/a "fivelitermustang" wrote in message news:7b******************************@localhost.ta lkaboutprogramming.com... Essentially what the program needs to do is split apart a large group of data and then it further splits apart the groups of data, etc... For example, Level 0 starts off with a large array data. The data is split apart into "n" groups. Then each group in there is also split apart into "n" groups and it continues on like that. For each branch of data the matrix is " Here is a quick picture I drew to illustrate what I'm doing: http://members.shaw.ca/fivelitermustang/split.gif [snip] It looks like you should be able to use the same code for all the splits, by using recursion. You can see from the diagram that in every case you are taking one "box" (whatever that might represent) and splitting it into two, so you should not need to do this differently from one level to another. Write a function that splits one box into two, and then recursively calls itself twice, once for each box that emerged from the split. You also need a way to terminate the recursion, i.e., some condition under which the function will just return without doing anything. DW Jul 22 '05 #3

 P: n/a "David White" wrote in message news:x9*****************@nasal.pacific.net.au... "fivelitermustang" wrote in message news:7b******************************@localhost.ta lkaboutprogramming.com... Essentially what the program needs to do is split apart a large group of data and then it further splits apart the groups of data, etc... For example, Level 0 starts off with a large array data. The data is split apart into "n" groups. Then each group in there is also split apart into "n" groups and it continues on like that. For each branch of data the matrix is " Here is a quick picture I drew to illustrate what I'm doing: http://members.shaw.ca/fivelitermustang/split.gif [snip] It looks like you should be able to use the same code for all the splits, by using recursion. You can see from the diagram that in every case you are taking one "box" (whatever that might represent) and splitting it into two, so you should not need to do this differently from one level to another. Write a function that splits one box into two, and then recursively calls itself twice, once for each box that emerged from the split. You also need a way to terminate the recursion, i.e., some condition under which the function will just return without doing anything. Here's an example. It's fixed at splitting into two pieces, but it can be modified to split into a variable number of pieces. #include #include struct Node { Node() : left(0), right(0) {} Node *left; Node *right; std::vector data; void Split(); void Show() { std::vector::const_iterator i = data.begin(); while(i != data.end()) { std::cout << *i << ' '; ++i; } std::cout << std::endl; } }; void Node::Split() { Show(); if(data.size() < 2) return; left = new Node; left->data.insert(left->data.begin(), data.begin(), data.begin() + data.size()/2); right = new Node; right->data.insert(right->data.begin(), data.begin() + data.size()/2, data.end()); left->Split(); right->Split(); } int main() { const int nums[] = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}; Node node; node.data.insert(node.data.begin(), nums, nums + sizeof(nums)/sizeof(nums[0])); node.Split(); } DW Jul 22 '05 #4

 P: n/a "fivelitermustang" wrote Essentially what the program needs to do is split apart a large group of data and then it further splits apart the groups of data, etc... For example, Level 0 starts off with a large array data. The data is split apart into "n" groups. Then each group in there is also split apart into "n" groups and it continues on like that. For each branch of data the matrix is " Here is a quick picture I drew to illustrate what I'm doing: http://members.shaw.ca/fivelitermustang/split.gif I have all the code written for the functions and things and I can make the program do what I need to do if I hardcode it but I need to program to be able to take in any type of dimensions of data and split into any number of levels defined by the user. I have already hardcoded the split from 0->1, which is fine. I need to be able to split the resulting matrices of data into further and further levels specified by the user. To calculate the split from 1->2 I must take each of the 2 branches of that matrix and split it into two pieces... yielding 4 branches on the next level. To calculate the split from 2->3 I must take each of the 4 branches of that matrix and split that into two pieces... yielding 8 branches on the next level. I also need to find a way to iterate through each branch infinitely many levels deep. The function needs to have the data passed in from level 1 to calculate level 2. When level two is calculated the function is called again with the blocks from level 2 to generate blocks in level 3. I am not sure how to do this... for example if the user wanted to split the data into 3 groups then the function to stem 3 more branches off each block would be used 3 times on the first level, then it would have to be used 9 times on the second level and then 27 times on the third level... etc... How would I mathematically implement that? In addition what would be a good way to store the data in each "block"... I'm thinking a three dimensional array where the first dimension is an index number and the last two dimensions store the actual information in that matrix. Somehow, the other posters got confused by the simplified diagram and assumed it was a binary tree. What you're describing is commonly called an "m-way tree" or "n-ary tree". The subset of balanced n-ary trees includes B-trees and B*-trees. There are also variants like B+-trees (mostly used for out-of-core indexing and actually a hybrid structure). Tries (from the word 'reTRIEve') are an unbalanced variant used for very fast (and memory-expensive) searching. All of these are explained in any good book on data structures. I recommend Sedgewick as a starting place. Claudio Puviani Jul 22 '05 #5