Prev: repeating elements in an array
Next: The trim function and its intented purpose?
From: none on 5 Apr 2010 19:51
Hi

Sorry if this is a FAQ, but I don't even know the correct terminology to
Google.

In general, how do you solve the "variable dimension" problem? I
understand that some languages support arbitrary-dimension arrays
intrinsically, as in Perl:

my $x;
$x[5][5][5][5][5][5] = 5;

And I understand that you can create similar behavior in more strict
languages, like C++, by creating an array class whose members can also be
arrays, thereby allowing array-of-array-of-array-etc...

But how do you go about writing code to deal with such objects? For
example, if I knew that my array was three levels deep, I could write the
following:

ThreeLevelArray A;
int x, y, z;

for (x = 0; x < A.size() x++)
{
for (y = 0; y < A[x].size(); y++)
{
for (z = 0; z < A[x][y].size(); z++)
{
A[x][y][z] = x + y + z;
}
}
}

But how do you get a variable number of nested for-loops, or the logical
equivalent of that? I'm really just looking for general advice on how to
deal with variable-dimension arrays. In the past, I've run into the
problem only a handful of times, and in each case I was able to do
something that worked but was very un-elegant and required heavy
assumptions about what the nature of the array would be.

Thanks in advance.
From: Kai-Uwe Bux on 5 Apr 2010 20:01
none wrote:

> Hi
>
> Sorry if this is a FAQ, but I don't even know the correct terminology to
> Google.
>
> In general, how do you solve the "variable dimension" problem? I
> understand that some languages support arbitrary-dimension arrays
> intrinsically, as in Perl:
>
> my $x;
> $x[5][5][5][5][5][5] = 5;
>
> And I understand that you can create similar behavior in more strict
> languages, like C++, by creating an array class whose members can also be
> arrays, thereby allowing array-of-array-of-array-etc...

Not in C++. Instead you could do something like:

typedef std::vector< unsigned long > multi_index;
typedef std::map< multi_index, T > sparse_variable_dim_array_of_T;


> But how do you go about writing code to deal with such objects? For
> example, if I knew that my array was three levels deep, I could write the
> following:
>
> ThreeLevelArray A;
> int x, y, z;
>
> for (x = 0; x < A.size() x++)
> {
> for (y = 0; y < A[x].size(); y++)
> {
> for (z = 0; z < A[x][y].size(); z++)
> {
> A[x][y][z] = x + y + z;
> }
> }
> }
>
> But how do you get a variable number of nested for-loops, or the logical
> equivalent of that?

You would not. Instead you would have a single loop from begin() to end()
over the map<> from above.

> I'm really just looking for general advice on how to
> deal with variable-dimension arrays. In the past, I've run into the
> problem only a handful of times, and in each case I was able to do
> something that worked but was very un-elegant and required heavy
> assumptions about what the nature of the array would be.


Best

Kai-Uwe Bux
From: Richard Heathfield on 5 Apr 2010 20:31
none wrote:

<snip>

> But how do you get a variable number of nested for-loops, or the logical
> equivalent of that?

"Programs and Data Structures in C", 2nd edition, Leendert Ammeraal,
Wiley 1992, reprinted 1996, page 79, code cited "as is". There are a
number of issues with the code that I am tempted to discuss, but I'll
refrain, and simply quote what he wrote:

/* NESTED.C: A variable number of nested loops
*/
#include <stdio.h>
#define LEN 10
int n, r[LEN], lower[LEN], upper[LEN];

void print_r(void)
{ int i;
for (i=0; i<n; i++) printf("%6d", r[i]);
puts("");
}

void f(int k)
{ if (k == n) print_r(); else
for (r[k] = lower[k]; r[k] <= upper[k]; r[k]++)
f(k+1);
}

main()
{ int i;
printf("Enter n (not greater than %d): ", LEN);
scanf("%d", &n);
puts("Enter n pairs (lower, upper):");
for (i=0; i<n; i++)
scanf("%d %d", lower + i, upper + i);
puts("\nOutput:\n");
for (i=0; i<n; i++) printf(" r[%d]", i);
puts("");
f(0);
return 0;
}

He shows a demo run, but I'm not going to bother typing it. Instead,
I'll compile the above and duplicate his results so that I can
copy-paste them here. (In case you're wondering, that's a sort of
self-check that I've copied his code correctly!)

Enter n (not greater than 10): 3
Enter n pairs (lower, upper):
5 7
2 2
8 9

Output:

r[0] r[1] r[2]
5 2 8
5 2 9
6 2 8
6 2 9
7 2 8
7 2 9

This doesn't /quite/ match Ammeraal's results - it looks like I missed a
space somewhere, so my results don't line up quite as prettily as his -
but the actual data are fine. As you can see, this is the equivalent of
writing:

for(i = 5; i <= 7; i++)
for(j = 2; j <= 2; j++)
for(k = 8; k <= 9; k++)
printf("%6d %6d %6d\n", i, j, k);

Now WITHOUT changing a single line of code, let's go for the equivalent of:

for(i = 5; i <= 7; i++)
for(j = 2; j <= 2; j++)
for(k = 8; k <= 9; k++)
for(l = 3; l <= 5; l++)
printf("%6d %6d %6d %6d\n", i, j, k, l);

So we run the program again, without having to change it - all we do is
specify different inputs:

Enter n (not greater than 10): 4
Enter n pairs (lower, upper):
5 7
2 2
8 9
3 5

Output:

r[0] r[1] r[2] r[3]
5 2 8 3
5 2 8 4
5 2 8 5
5 2 9 3
5 2 9 4
5 2 9 5
6 2 8 3
6 2 8 4
6 2 8 5
6 2 9 3
6 2 9 4
6 2 9 5
7 2 8 3
7 2 8 4
7 2 8 5
7 2 9 3
7 2 9 4
7 2 9 5

This may or may not be what you want, but I hope it's a step in the
right direction.

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
"Usenet is a strange place" - dmr 29 July 1999
Sig line vacant - apply within
From: Andrew Poelstra on 6 Apr 2010 01:31
On 2010-04-05, none <none(a)none.none> wrote:
>
> But how do you get a variable number of nested for-loops, or the logical
> equivalent of that? I'm really just looking for general advice on how to
> deal with variable-dimension arrays. In the past, I've run into the
> problem only a handful of times, and in each case I was able to do
> something that worked but was very un-elegant and required heavy
> assumptions about what the nature of the array would be.
>
> Thanks in advance.

Use recursion:

void recurse(my_array) {
for(elem in my_array)
recurse(elem);
}

You might need to add a check to see if you are at the deepest
possible depth, and do some actual work instead of just recursing
again, but that's the worst sort of hackery required in general.

--
Andrew Poelstra
http://www.wpsoftware.net/andrew
From: none on 6 Apr 2010 02:49
Kai-Uwe Bux wrote:

>> And I understand that you can create similar behavior in more strict
>> languages, like C++, by creating an array class whose members can
>> also be arrays, thereby allowing array-of-array-of-array-etc...
>
> Not in C++. Instead you could do something like:

When you say "Not in C++," do you mean that you *can't* do that in C++
or that you *shouldn't* do that in C++ because it doesn't follow the
"spirit" of C++? If you mean the former, I have to disagree because
I've done it, more than once. I can post sample code if needed, but all
you have to do is create a class that contains a vector of pointers to
the same class. You can even make your arrays behave similarly to perl
arrays by having your class's [] operator perform an allocation when
invoked on a node that doesn't already exist. Then, syntax like this
becomes perfectly legal:

MyArrayOfArrayClass x;
x[2][3][4][5][6] = 7;

The array x now has six dimensions and (depending on how you define the
semantics of your [] operator) a total of 720 elements.

> typedef std::vector< unsigned long > multi_index;
> typedef std::map< multi_index, T > sparse_variable_dim_array_of_T;

This is interesting. You get a map with whatever element type you like,
with a key that is a vector. So how would you assign elements into your
map? I don't believe that C++ allows anything like this:

x[{1, 2, 3, 4, 5}] = 6;

Having to create and initialize a vector just to use it as an index
every time you want to access the map would be cumbersome:

std::vector key;
key.push_back(1);
key.push_back(2);
key.push_back(3);
key.push_back(4);
key.push_back(5);
x[key] = 6;

I suppose there's a more elegant way, maybe like this:

unsigned long indices[5] = {1, 2, 3, 4, 5};
std::vector key(indices, &indices[5]}; // (first, last) constructor
x[key] = 6;

It's still a bit awkward. Maybe it's possible to create a class with an
overloaded [] operator that could build the vector, then use it as the
look-up into the map, so that the above could be written as:

x[1][2][3][4][5] = 6;

It's not obvious to me how (if) that could be done, though.
 |  Next  |  Last
Pages: 1 2 3
Prev: repeating elements in an array
Next: The trim function and its intented purpose?