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?

I don't understand why you are iterating over the same elements so many times. There are only 2*800 = 1,600 elements, but you are iterating 640,000 times. You are therefore visiting each element many times. — Matthew Watson
– Matthew Watson, Commented Jul 14, 2018 at 10:34
you need a 2nd loop...because you need to loop through the columns — Ctznkane525
– Ctznkane525, Commented Jul 14, 2018 at 10:58
@MatthewWatson That's a good question. My end goal is to iterate through all possible combinations of values. It is not enough to just get the necessary element from within an array. It's as you said - there are only 1600 elements total, but these 1600 elements can create 640000 unique combinations. — Alex
– Alex, Commented Jul 14, 2018 at 12:34
Ah, so what you want is every combination of one element from each column. — Matthew Watson
– Matthew Watson, Commented Jul 14, 2018 at 12:56

Wattanapong Suttapak · Accepted Answer · 2018-07-14 11:44:28Z

3

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);
        }

answered Jul 14, 2018 at 11:44

Wattanapong Suttapak

1111 silver badge2 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Alex Over a year ago

That's what I like about Java. The syntax is very similar to C#! I was on planning executing the loop using the CUDA, so I will modify the code slightly for C/C++. You solution works great! Thank you!

Matthew Watson · Accepted Answer · 2018-07-14 13:43:30Z

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}));
        }
    }
}

Collectives™ on Stack Overflow

looping over multidimensional array in a single loop

2 Answers 2

1 Comment

Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Related