By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
449,081 Members | 861 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 449,081 IT Pros & Developers. It's quick & easy.

How to create an N dimensional array with N elements?

P: n/a
BCC
Ive been googling and reading through my books but I haven't figured out a
solution (much less an elegant one) to create a multidimensional array with
a runtime determined number of dimensions. I also checked out the
boost::multi_array.hpp, and Giovanni Bavistrelli's Array code. Neither of
these seem to allow dynamic array dimensions.

For example, the user selects a 2 dimensional array, I want to create:
MyObject** array = new MyObject[dim1_size][dim2_size];

And if they select a 4 dim array:
MyObject**** array = new
MyObject[dim1_size][dim2_size][dim3_size][dim4_size];

Besides using bigugly if statements, how do I do this?

Thanks,
Bryan
Jul 22 '05 #1
Share this Question
Share on Google+
10 Replies


P: n/a
BCC
Upon further reflection, I think creating an n dimensional array may be
besides the point...

What I am trying to do, at the end of the day, is to take a list of objects
(lets just say they are ints for the moment though) and multiply it by
itself N number of times.

So if I have an array with 10 elements in it, I need to create a new list
with 100 elements in it, and populate those 100 elements with the results
of:
[0][0] * [0][0]
[0][0] * [0][1]
etc. etc.

With 3 dims, the list would be 10000 elements long, and so on.

If this was a nested for loop, with N number of nests this would be
simple... but without knowing ahead of time how many loops to use Im not
sure how to go about this.

Any suggestions?
Thanks
B
Jul 22 '05 #2

P: n/a

"BCC" <br***@akanta.com> wrote in message
news:zI*****************@newssvr25.news.prodigy.co m...
Upon further reflection, I think creating an n dimensional array may be
besides the point...

What I am trying to do, at the end of the day, is to take a list of objects (lets just say they are ints for the moment though) and multiply it by
itself N number of times.

So if I have an array with 10 elements in it, I need to create a new list
with 100 elements in it, and populate those 100 elements with the results
of:
[0][0] * [0][0]
[0][0] * [0][1]
etc. etc.

With 3 dims, the list would be 10000 elements long, and so on.

If this was a nested for loop, with N number of nests this would be
simple... but without knowing ahead of time how many loops to use Im not
sure how to go about this.

Any suggestions?


Recursion.

Not completely sure this is what you are asking for but hopefully will be
close enough for you to adapt.

#include <algorithm>
#include <iterator>
#include <iostream>
#include <list>
using namespace std;

void generate(std::list<int>& res, std::list<int> const& l, int depth, int
value = 1)
{
if (depth == 0)
{
res.push_back(value);
}
else
{
for (std::list<int>::const_iterator i = l.begin(); i != l.end(); ++i)
generate(res, l, depth - 1, value*(*i));
}
}

int main()
{
// setup starting list
std::list<int> l;
l.push_back(1);
l.push_back(2);
l.push_back(3);
// generate result list
std::list<int> res;
generate(res, l, 4);
// print results
std::copy(res.begin(), res.end(), std::ostream_iterator<int>(std::cout, "
"));
}

john
Jul 22 '05 #3

P: n/a
BCC wrote:
Upon further reflection, I think creating an n dimensional array may be
besides the point...

What I am trying to do, at the end of the day, is to take a list of objects
(lets just say they are ints for the moment though) and multiply it by
itself N number of times.

So if I have an array with 10 elements in it, I need to create a new list
with 100 elements in it, and populate those 100 elements with the results
of:
[0][0] * [0][0]
[0][0] * [0][1]
etc. etc.

With 3 dims, the list would be 10000 elements long, and so on.

If this was a nested for loop, with N number of nests this would be
simple... but without knowing ahead of time how many loops to use Im not
sure how to go about this.

Any suggestions?


Recursion.
Jul 22 '05 #4

P: n/a
BCC
Hi John, thanks very much for the suggestion- you were pretty close to what
I need, but it is still tripping me up. Heres what I have:

int depth = 2;
int list_size = 5;
int* array = new int[list_size];
for (int i = 0; i < list_size; ++i) array[i] = 0;
vector<int *> all_list;

Generate(all_list, list_size, depth, array);

// Process array

delete [] array;

void Generate(std::vector<int *>& res, int list_size, int depth, int*
in_list)
{
if (depth == 0)
{
res.push_back(in_list);
}
else {
for (int i = 0; i < list_size; ++i) {
if (in_list[i] > 0) continue; // We have already included this seq,
skip
++in_list[i];
Generate(res, list_size, depth - 1, in_list);
}
}
}

What I need it to have is in my resulting list is list_size^depth patterns,
or in this case all unique possible combinations of 1's and 2's:
for 1's
10000
01000
00100
00010
00001
-And-
for 2's
11000
10100
10010
10001
01100
01010
01001
00110
00101
00011

I believe this is all of them. And I need to be able to do this for any
size list and any depth...

I think the function is pretty close, but I am still not getting it. What
am I missing? (hopefully this makes sense!)

Thanks,
Bryan
Jul 22 '05 #5

P: n/a
"BCC" <br***@akanta.com> wrote in message
news:it***************@newssvr27.news.prodigy.com. ..
Hi John, thanks very much for the suggestion- you were pretty close to what I need, but it is still tripping me up. Heres what I have:

int depth = 2;
int list_size = 5;
int* array = new int[list_size];
for (int i = 0; i < list_size; ++i) array[i] = 0;
vector<int *> all_list;

Generate(all_list, list_size, depth, array);

// Process array

delete [] array;

void Generate(std::vector<int *>& res, int list_size, int depth, int*
in_list)
{
if (depth == 0)
{
res.push_back(in_list);
}
else {
for (int i = 0; i < list_size; ++i) {
if (in_list[i] > 0) continue; // We have already included this seq,
skip
++in_list[i];
Generate(res, list_size, depth - 1, in_list);
}
}
}

What I need it to have is in my resulting list is list_size^depth patterns, or in this case all unique possible combinations of 1's and 2's:
for 1's
10000
01000
00100
00010
00001
-And-
for 2's
11000
10100
10010
10001
01100
01010
01001
00110
00101
00011


It looks as though all you need is a combination generator, so a Combination
class could do the job (with a Next() member returns the next combination)
and you could forget about the recursion.

DW

Jul 22 '05 #6

P: n/a

"BCC" <br***@akanta.com> wrote in message
news:it***************@newssvr27.news.prodigy.com. ..
Hi John, thanks very much for the suggestion- you were pretty close to what I need, but it is still tripping me up. Heres what I have:

int depth = 2;
int list_size = 5;
int* array = new int[list_size];
for (int i = 0; i < list_size; ++i) array[i] = 0;
vector<int *> all_list;

Generate(all_list, list_size, depth, array);

// Process array

delete [] array;

void Generate(std::vector<int *>& res, int list_size, int depth, int*
in_list)
{
if (depth == 0)
{
res.push_back(in_list);
}
else {
for (int i = 0; i < list_size; ++i) {
if (in_list[i] > 0) continue; // We have already included this seq,
skip
++in_list[i];
Generate(res, list_size, depth - 1, in_list);
}
}
}

What I need it to have is in my resulting list is list_size^depth patterns, or in this case all unique possible combinations of 1's and 2's:
for 1's
10000
01000
00100
00010
00001
-And-
for 2's
11000
10100
10010
10001
01100
01010
01001
00110
00101
00011

I believe this is all of them. And I need to be able to do this for any
size list and any depth...

I think the function is pretty close, but I am still not getting it. What
am I missing? (hopefully this makes sense!)


Actually no. When I read your first post I thought you were talking about
combinations, and for combinations a recusrive algorithm is normally the way
to go. But now I see that you are talking about permutations (i.e. unique
combinations) and for permutations an iterative algorithm is correct. It's
quite hard to work out the correct algorithm for permutations but
fortunately its already been done in the STL next_permutation function (look
at the code in the <algorithm> header if you are interested).

The other thing that worries me about your code is that you have a vector of
pointers and you are repeatedly pushing the same pointer onto your vector,
which cannot be a good idea.

Here's some code, I switched to a vector of vectors, instead of a vector of
pointers.

#include <algorithm>
#include <iterator>
#include <iostream>
#include <vector>

int main()
{
int depth = 2;
int list_size = 5;
std::vector<std::vector<int> > all_list;
std::vector<int> array(list_size);
for (int i = 1; i <= depth; ++i)
{
// set up initial permutation
for (int j = 0; j < list_size; ++j)
array[j] = j < list_size - i ? 0 : 1;
// add all permutations of this type
do
{
all_list.push_back(array);
}
while (next_permutation(array.begin(), array.end()));
}
// print results
for (std::vector<std::vector<int> >::const_iterator i = all_list.begin();
i != all_list.end(); ++i)
{
std::copy(i->begin(), i->end(), std::ostream_iterator<int>(std::cout, "
"));
std::cout << '\n';
}
}
Jul 22 '05 #7

P: n/a
> >
I think the function is pretty close, but I am still not getting it. What am I missing? (hopefully this makes sense!)


Actually no.


I meant, 'no its not close', not 'no it doesn't make sense'. No offence
intended.

john
Jul 22 '05 #8

P: n/a
"John Harrison" <jo*************@hotmail.com> wrote in message
news:2j*************@uni-berlin.de...

"BCC" <br***@akanta.com> wrote in message
news:it***************@newssvr27.news.prodigy.com. ..
10000
01000
00100
00010
00001
-And-
for 2's
11000
10100
10010
10001
01100
01010
01001
00110
00101
00011

I believe this is all of them. And I need to be able to do this for any
size list and any depth...

I think the function is pretty close, but I am still not getting it. What am I missing? (hopefully this makes sense!)
Actually no. When I read your first post I thought you were talking about
combinations, and for combinations a recusrive algorithm is normally the

way to go. But now I see that you are talking about permutations (i.e. unique
combinations)


Those look like combinations above to me, not permutations (i.e., order
matters for permutations but not combinations), or are you referring to some
other aspect of the problem?

DW

Jul 22 '05 #9

P: n/a
BCC
> Actually no. When I read your first post I thought you were talking about
combinations, and for combinations a recusrive algorithm is normally the way to go. But now I see that you are talking about permutations (i.e. unique
combinations) and for permutations an iterative algorithm is correct. It's
quite hard to work out the correct algorithm for permutations but
fortunately its already been done in the STL next_permutation function (look at the code in the <algorithm> header if you are interested).
Ah, that is a nice tip, I didnt know next_permutation existed, very useful
and I will most certainly look at the code for this.
The other thing that worries me about your code is that you have a vector of pointers and you are repeatedly pushing the same pointer onto your vector,
which cannot be a good idea.


Agreed. I was thinking in terms of speed (since STL vector is slow), but
with my list sizes I dont imagine that performance will be a problem at all.

And the code is great to get me started.

Thanks for all the help!

Bryan
Jul 22 '05 #10

P: n/a
>
Those look like combinations above to me, not permutations (i.e., order
matters for permutations but not combinations), or are you referring to some other aspect of the problem?


Not sure, sometimes I confuse myself. Still the OP seems happy, and there no
doubt that my use of the STL function next_permutation produced exactly the
output he required.

john
Jul 22 '05 #11

This discussion thread is closed

Replies have been disabled for this discussion.