Looping through a n-dimensional array

Question

I have a generic multidimensional array having different dimensions. I need to loop through it in order to save for each element the relative array of indices and the relative value.

In the case of an array of two dimensions, let's say 4 and 5, it would be trivial:

        var d1 = 4;
        var d2 = 5;
        var array = Array.CreateInstance(typeof (int), new[] {d1, d2});

        //...
        // code for populating array
        //...

        for (int i = 0; i < d1; i++)
        {
            for (int j = 0; j < d2; j++)
            {
                var value = array.GetValue(new[] { i, j });
                var indices = new[] {i, j};
            }
        }

But I need to do the same thing with an array of n different dimensions. How can I achieve it? Do I need to implement a recursive function?

Answer 1

Visiting all elements in a multidimensional array is not difficult. You can simply do a flat iteration through the entire array with a single index. The tricky part is mapping this single index to the corresponding multidimensional coordinates.

In general, given a matrix with size vector D, the ith single indexed element of this matrix has a coordinate vector C_i, such that:

For 0 <= n < size(D).

Implementing this, the IndexToCoordinates method is:

static int[] IndexToCoordinates(int i, Array arr)
{
    var dims = Enumerable.Range(0, arr.Rank)
        .Select(arr.GetLength)
        .ToArray();

    Func<int, int, int> product = (i1, i2) => i1 * i2;

    return dims.Select((d, n) => (i/dims.Take(n).Aggregate(1, product))%d).ToArray();
}

Now, for example, if you wanted to visit every item in a multidimensional array and output its coordinates, you could do:

static void OutputAllArrayIndices(Array arr)
{
    var i = 0;

    foreach (int item in arr)
    {
        var coords = IndexToCoordinates(i++, arr);
        Console.WriteLine(string.Join(", ", coords));
    }
}

Running OutputAllArrayIndices(new int[3, 2, 4]) then produces:

0, 0, 0
1, 0, 0
2, 0, 0
3, 0, 0
0, 1, 0
1, 1, 0
2, 1, 0
3, 1, 0
0, 0, 1
1, 0, 1
2, 0, 1
3, 0, 1
0, 1, 1
1, 1, 1
2, 1, 1
3, 1, 1
0, 0, 2
1, 0, 2
2, 0, 2
3, 0, 2
0, 1, 2
1, 1, 2
2, 1, 2
3, 1, 2