CODEWITHSUNDEEP
algorithmmultidimensional-array
user401247
user401247

Reputation:

Iterate elements of an n-demensional array

I need to iterate over an n-dimensional array of numbers where n is only known at runtime. For example, an array of dimensions (2,4,6,5). This has 240 elements and I'd like to be able to iterate over the i, j, k, and l indices. I could flatten the data and access it linearly, but then I'd need to know how a specific point in the linear array related to a coordinate, i, j, k l, which I'm not sure how to do.

Often for fixed n such as 2D or 3D, we'd use nested for loops. But with n unknown, it's not possible to do that. Can anyone point me to information on this? I've tried searching multiple times but I get topics like iterating over a list, where the sublists are objects and can iterate those recursively. But in this case, the array is a simple array of numbers. I'm currently stuck.

Upvotes: 1

Views: 152

Answers (1)

maraca
maraca

Reputation: 8743

For an n-dimensional array with dimensions d = [d0, d1, d2, ..., d(n-1)] you can get the ith element the following way:

  1. Build the product of the dimensions from right to left (p[0] is not needed but it tells you how many values are in the array):

    p[n - 1] = d[n - 1]
for (j = n - 2; j >= 0; j--)
    p[j] = p[j + 1] * d[j]

  2. Now you can get get the indexes the following way:

    for (j = 0; j < n - 1; j++) {
    index[j] = i / p[j + 1] // integer division or use floor i.e. round down
    i = i % p[j + 1]
}
index[n - 1] = i

And to answer the other question, how to iterate? Depends on the programming language. Recursion is a possibility. Pseudo-code:

function iterate(arr) {
    if (isArray(arr)) {
        for (a in arr) {
            iterate(a)
        }
    } else {
        // do something with value arr
    }
}

The above also works if every element in an array can be an array of any dimension or a value. The index calculation on the other hand doesn't work in that case.

Alternative, if ther is no isArray():

function iterate(arr, dimensions, depth) {
    if (depth < dimensions.length) {
        for (i = 0; i < dimensions[depth]; i++) {
            iterate(arr[i], dimensions, depth + 1)
        }
    } else {
        // do something with value arr
    }
}

Upvotes: 0

Related Questions