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.

Eric Lippert · Accepted Answer · 2013-09-03 20:04:04Z

3

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

edited Sep 3, 2013 at 20:04

Eric Lippert

663k185 gold badges1.3k silver badges2.1k bronze badges

answered Jun 23, 2013 at 2:14

jason

243k36 gold badges437 silver badges532 bronze badges

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

8 Comments

ron Over a year ago

Hi Jason, I tried using the codes in the blog, but I still can't get the combinations. Sorry, since I am new in C# coding. :(

jason Over a year ago

@Ron Reyes: Sorry to hear that. My code works as is, combined with Eric's code, but I've provided you a full sample nonetheless.

ron Over a year ago

Ok, I'll Try it again, I just don't know how to see the results using Console.WriteLine.

jason Over a year ago

@Ron Reyes: I'm not sure what you mean. In Visual Studio, start a new solution, make it a console application, and paste the code above exactly as. Then, compile and run the application.

ron Over a year ago

It shows this in the output: System.Linq.Enumerable+<ConcatIterator>d__71`1[System.Int32]

|

Collectives™ on Stack Overflow

Dynamic Generation of All Possible Combinations of Index of an Array

1 Answer 1

8 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

8 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related