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.

score 3 · Accepted Answer · edited Sep 03 '13 at 20:04

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 03 '13 at 20:04

Eric Lippert

647,829
179
1,238
2,067

answered Jun 23 '13 at 02:14

jason

236,483
35
423
525

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. :( – ron Jun 23 '13 at 12:55
@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. – jason Jun 23 '13 at 13:14
Ok, I'll Try it again, I just don't know how to see the results using Console.WriteLine. – ron Jun 23 '13 at 13:17
@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. – jason Jun 23 '13 at 13:21
It shows this in the output: System.Linq.Enumerable+d__71`1[System.Int32] – ron Jun 23 '13 at 13:27
@ron: I don't think that you pasted the code exactly as is. In particular, I think that you changed `Console.WriteLine(String.Join(",", index));` to `Console.WriteLine(index);`. `index` is a sequence of specific coordinates into the array, so it looks like `(0, 1, 2)`, for example. If you try to print out `index`, you get the type of `index`, which is concrete a `IEnumerable` from Eric's code. You have to format that sequence into a meaningful `string`. One way to do that is iterate over the sequence adding a comma between entries. `String.Join` is a simple way to do that. – jason Jun 23 '13 at 13:50
I tried running your codes as is in .NET Framework 4.5 and it works fine. I think I get the error "The best overloaded method match for 'string.Join(string, string[])' has some invalid arguments" and "Argument 2: cannot convert from 'System.Collections.Generic.IEnumerable' to 'string[]'" because I tried to run it at .NET Framework 3.5. – ron Jun 23 '13 at 13:58
@ron: Yes, the overload of `String.Join` that I'm using wasn't added until .NET 4.5. If you need to use .NET 3.5, change `index` to `index.Select(x => x.ToString()).ToArray()` in the call to `String.Join`. This is covered [here](http://stackoverflow.com/a/1890104/45914). – jason Jun 23 '13 at 14:03

Dynamic Generation of All Possible Combinations of Index of an Array

1 Answers1

Linked