How to iterate over n dimensions

algorithmarraysdimensionloops

How can I iterate over a n-dimensional array given the number of dimensions and the size of each as variables?

int n;
int size[n];

Since the number of dimensions is not fixed, I cannot write a nested loop for each dimension. I need the code to work with each number of dimensions.

In addition, it doesn't matter weather the actual data is stored in a n-dimensional array or a flat array containing all the data in a large row. Both are acceptable.

int data[16][42][14];   // n-dimensional array
int data[16 * 42 * 14]; // flat array containing the same data

Best Answer

You could use recursion, for each dimension "guess" its index and recursively invoke on a smaller problem, something along the lines of (peudo code):

iterate(d,n,size,res):
   if (d >= n): //stop clause
       print res
       return
   for each i from 0 to size[d]:
       res.append(i) //append the "guess" for this dimension
       iterate(d+1,n,size,res)
       res.removeLast //clean up environment before next iteration

where:

  • d is the currently visited dimension
  • size,n is the input
  • res is a vector representing the current partial result

invoke with iterate(0,n,size,res), where res is initialized to an empty list.

C++ code should be something like:

void iterate(int d,int n,int size[], int res[]) {
    if (d >= n) { //stop clause
       print(res,n);
       return;
   }
   for (int i = 0; i < size[d]; i++) { 
       res[d] = i;
       iterate(d+1,n,size,res);
   }
}

full code and a simple example are available on ideone

Related Topic