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

Discussion in 'C++' started by fivelitermustang, May 20, 2004.

  1. 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.
     
    fivelitermustang, May 20, 2004
    #1
    1. Advertising

  2. fivelitermustang

    Bruce Guest

    In comp.lang.c++
    "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


    That is a binary tree. Most solutions involve recursion. There should be
    source code all over the net for them.
     
    Bruce, May 20, 2004
    #2
    1. Advertising

  3. fivelitermustang

    David White Guest

    "fivelitermustang" <> wrote in message
    news:...
    > 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, May 20, 2004
    #3
  4. fivelitermustang

    David White Guest

    "David White" <> wrote in message
    news:x9Yqc.2482$...
    > "fivelitermustang" <> wrote in message
    >

    news:...
    > > 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
     
    David White, May 20, 2004
    #4
  5. "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
     
    Claudio Puviani, May 20, 2004
    #5
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. mit
    Replies:
    0
    Views:
    437
  2. sumit chawla
    Replies:
    0
    Views:
    522
    sumit chawla
    Aug 3, 2004
  3. Scott Chapman
    Replies:
    6
    Views:
    449
    John J. Lee
    Sep 8, 2003
  4. Maxwell Hammer
    Replies:
    7
    Views:
    659
    Peter Hansen
    Jun 18, 2005
  5. PowerStudent
    Replies:
    4
    Views:
    317
    Juha Nieminen
    Aug 2, 2010
Loading...

Share This Page