Dynamic Generation of All Possible Combinations of Index of an Array

Question

My task is to generate all possible index combinations of an array, wherein the array might be a single, 2D, 3D, 4D ... nD array with different number of elements. For now, I can only support single, 2D and 3D array using nested for loop.

Example:

byte[,,] sampleArray = new byte[5,4,3];

Generated Index Combinations:
sampleArray[0,0,0]
sampleArray[0,0,1]
sampleArray[0,0,2]
sampleArray[0,1,0]
sampleArray[0,1,1]
sampleArray[0,1,2]
sampleArray[0,2,0]
sampleArray[0,2,1]
sampleArray[0,2,2]
sampleArray[0,3,0]
sampleArray[0,3,1]
sampleArray[0,3,2]
sampleArray[1,0,0]
sampleArray[1,0,1]
sampleArray[1,0,2]
sampleArray[1,1,0]
sampleArray[1,1,1]
sampleArray[1,1,2]
sampleArray[1,2,0]
sampleArray[1,2,1]
sampleArray[1,2,2]
sampleArray[1,3,0]
sampleArray[1,3,1]
sampleArray[1,3,2]
sampleArray[2,0,0]
sampleArray[2,0,1]
sampleArray[2,0,2]
sampleArray[2,1,0]
sampleArray[2,1,1]
sampleArray[2,1,2]
sampleArray[2,2,0]
sampleArray[2,2,1]
sampleArray[2,2,2]
sampleArray[2,3,0]
sampleArray[2,3,1]
sampleArray[2,3,2]
sampleArray[3,0,0]
sampleArray[3,0,1]
sampleArray[3,0,2]
sampleArray[3,1,0]
sampleArray[3,1,1]
sampleArray[3,1,2]
sampleArray[3,2,0]
sampleArray[3,2,1]
sampleArray[3,2,2]
sampleArray[3,3,0]
sampleArray[3,3,1]
sampleArray[3,3,2]
sampleArray[4,0,0]
sampleArray[4,0,1]
sampleArray[4,0,2]
sampleArray[4,1,0]
sampleArray[4,1,1]
sampleArray[4,1,2]
sampleArray[4,2,0]
sampleArray[4,2,1]
sampleArray[4,2,2]
sampleArray[4,3,0]
sampleArray[4,3,1]
sampleArray[4,3,2]

My Code:

     protected void GenerateIndexCombinations(int indexCounter, 
     ref List<List<int>> indexList, Array arr, ref List<int> index)
        {
            int dimSize1 = arr.GetLength(0);
            int dimSize2 = 0;
            int dimSize3 = 0;
            if (indexCounter > 1)
            {
                dimSize2 = arr.GetLength(1);
                if (indexCounter > 2)
                {
                    dimSize3 = arr.GetLength(2);
                }
            }

            for (int a = 0; a < dimSize1; a++)
            {
                if (dimSize2 > 0)
                {
                    for (int b = 0; b < dimSize2; b++)
                    {
                        if (dimSize3 > 0)
                        {
                            for (int c = 0; c < dimSize3; c++)
                            {
                                index = new List<int>();
                                index.Add(a);
                                index.Add(b);
                                index.Add(c);
                                indexList.Add(index);
                            }
                        }
                        else
                        {
                            index = new List<int>();
                            index.Add(a);
                            index.Add(b);
                            indexList.Add(index);
                        }
                    }
                }
                else
                {
                    index = new List<int>();
                    index.Add(a);
                    indexList.Add(index);
                }
            }
        }

Where:
int indexCounter is number of dimension.
Array arr is the array accessed by using reflection:

Array arr = fieldInfoArray[j].GetValue(_classInstance) as Array;

ref List<List<int>> indexList will be the container of the combinations.
ref List<int> index is the individual number added to the indexList.

Since the dimension size is not fixed, as well the number of elements per dimension, I want to generate the combinations dynamically to replace my nested for loop, Is there a way to do it?

Thanks for your answers.

Answer 1

Eric Lippert has blogged about exactly this problem. In your specific case you're looking for the Cartesian product of Enumerable.Range(0, 5), Enumerable.Range(0, 4), and Enumerable.Range(0, 3). In general, you want something like this:

var dimensions = 
     Enumerable.Range(0, array.Rank)
               .Select(r => Enumerable.Range(0, array.GetLength(r)));

And then invoke Eric's method on dimensions. Here, I'm using Array.Rank to get the dimensionality of the matrix, and then using Array.GetLength to get the length along each dimension, and then dynamically generating the sequences that we need to compute the Cartesian product of. So, for each dimension, we project that dimension to the sequence of valid indexes along that dimension for array. Thus, for

T[,,...,] array = new T[a_1, a_2, ..., a_n];

we end up with dimensions equaling the sequence

(Enumerable.Range(0, a_1),
 Enumerable.Range(0, a_2),
 .
 .
 .,
 Enumerable.Range(0, a_n)
)

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

static class EnumerableExtensions {
    // credit: Eric Lippert
    public 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 })
        );
    }
}

class Program {
    public static void Main(string[] args) {
        int[,,] array = new int[5, 4, 3];
        var dimensions = 
            Enumerable.Range(0, array.Rank)
                      .Select(r => Enumerable.Range(0, array.GetLength(r)));
        var indexes = dimensions.CartesianProduct();
        foreach(var index in indexes) {
            Console.WriteLine(String.Join(",", index));
        }
    }
}