looping over multidimensional array in a single loop

Question

Imagine there to be a multidimensional array with 2 columns, each column having exact same element count:

int[,] virtualArray = new int[800,2];

If I were to iterate over such array in a single loop - I would then do something like:

int columnCount = 2;
int eachColumnElementCount = 800;
int totalCombinationCount = Convert.ToInt32(Math.Pow(eachColumnElementCount, columnCount)); // 640_000

for(int i = 0; i < totalCombinationCount ; i++) {
        int columnOneIndex= index / totalCombinationCount ;
        int columnTwoIndex= index - totalCombinationCount * eachColumnElementCount;
}

The results will be:

0,0 (i = 0)

0,1

..

0,799 (i = 799)

1,0 (i = 800)

1,1

..

1,799

..

799,799 (i = 640_000 - 1)

Now, I would like to extend my current implementation, to iterate in a single-dimensional loop - over a multidimensional array with 3 columns! I.e. the expected result, given, that we have the same 800 element count in each column, shall be following:

int[,] virtualArray = new int[800,3];

int columnCount = 3;
int eachColumnElementCount = 800;
int totalCombinationCount = Convert.ToInt32(Math.Pow(eachColumnElementCount, columnCount)); // 512_000_000

for(int i = 0; i < totalCombinationCount ; i++) {
        // int index1 = 0; // ??
        // int index2 = 0; // ??
        // int index3 = 0; // ??
}

0,0,0 (i = 0)

0,0,1

...

0,0,799

...

10,80,156

...

799,799,799 (i = 512_000_000 - 1)

I can not come up with a formula for the case when there are 3 columns.. Is there a way to loop over such array in a single loop?

Answer 1

I know you asked how to do this for three columns, but if you want to generalise this to work with N columns, it gets a little tricker.

What you are calculating is what's known as a Cartesian Product.

Eric Lippert posted a Linq solution to this in his blog.

It looks like this:

static IEnumerable<IEnumerable<T>> CartesianProduct<T>
    (this IEnumerable<IEnumerable<T>> sequences)
{
    IEnumerable<IEnumerable<T>> emptyProduct = new[] { Enumerable.Empty<T>() };

    return sequences.Aggregate(
        emptyProduct,
        (accumulator, sequence) =>
            from accseq in accumulator
            from item in sequence
            select accseq.Concat(new[]{item}));
}

(Please read Eric Lippert's blog post I linked above for full details on how this works.)

In order to use this approach with a 2D array, we need a way to iterate over the contents of the array by column rather than by row:

public static IEnumerable<T> Column<T>(T[,] array, int column)
{
    for (int row = array.GetLowerBound(0); row <= array.GetUpperBound(0); ++row)
        yield return array[row, column];
}

public static IEnumerable<IEnumerable<T>> ByColumn<T>(T[,] array)
{
    for (int column = array.GetLowerBound(1); column <= array.GetUpperBound(1); ++column)
        yield return Column(array, column);
}

Then we can solve a 5x4 array like so:

char[,] array =
{
    { 'A', 'F', 'K', 'P' },
    { 'B', 'G', 'L', 'Q' },
    { 'C', 'H', 'M', 'R' },
    { 'D', 'I', 'N', 'S' },
    { 'E', 'J', 'O', 'T' },
};

foreach (var combination in CartesianProduct(ByColumn(array)))
    Console.WriteLine(string.Concat(combination));

Note that you don't need to write different code for different number of columns - this works for any number of columns greater than one.

Putting the whole thing together in a simple console app:

using System;
using System.Collections.Generic;
using System.Linq;

namespace Demo
{
    static class Program
    {
        static void Main()
        {
            char[,] array =
            {
                { 'A', 'F', 'K', 'P' },
                { 'B', 'G', 'L', 'Q' },
                { 'C', 'H', 'M', 'R' },
                { 'D', 'I', 'N', 'S' },
                { 'E', 'J', 'O', 'T' },
            };

            foreach (var combination in CartesianProduct(ByColumn(array)))
                Console.WriteLine(string.Concat(combination));
        }

        public static IEnumerable<T> Column<T>(T[,] array, int column)
        {
            for (int row = array.GetLowerBound(0); row <= array.GetUpperBound(0); ++row)
                yield return array[row, column];
        }

        public static IEnumerable<IEnumerable<T>> ByColumn<T>(T[,] array)
        {
            for (int column = array.GetLowerBound(1); column <= array.GetUpperBound(1); ++column)
                yield return Column(array, column);
        }

        static IEnumerable<IEnumerable<T>> CartesianProduct<T>
            (this IEnumerable<IEnumerable<T>> sequences)
        {
            IEnumerable<IEnumerable<T>> emptyProduct = new[] { Enumerable.Empty<T>() };

            return sequences.Aggregate(
                emptyProduct,
                (accumulator, sequence) =>
                    from accseq in accumulator
                    from item in sequence
                    select accseq.Concat(new[]{item}));
        }
    }
}

Answer 2

Of course you can, try this Java code:

int columnCount = 3;
        int eachColumnElementCount = 800;
        int totalCombinationCount = (int)Math.pow(eachColumnElementCount, columnCount); // 800*800*800

        for(int i = 0; i < totalCombinationCount ; i++) {
                int column1Index= i % eachColumnElementCount;
                int column2Index= i / eachColumnElementCount % eachColumnElementCount ;
                int column3Index= i / eachColumnElementCount / eachColumnElementCount ;
                System.out.println(column3Index+","+column2Index+","+column1Index);
        }