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

[fivelitermustang]

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.

 

[Bruce]

In comp.lang.c++

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

That is a binary tree. Most solutions involve recursion. There should be
source code all over the net for them.

 

[David White]

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

 

[David White]

news:7b24a8b621707462a2953bba3987007b@localhost.talkaboutprogramming.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 <iostream>
#include <vector>

struct Node
{
Node() : left(0), right(0) {}
Node *left;
Node *right;
std::vector<int> data;
void Split();
void Show()
{
std::vector<int>::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

 

[Claudio Puviani]

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