Dynamic number of nested for loops to list unique combinations of objects

Question

I have n number of lists of objects which I need to convert to a list of object arrays each containing a unique combination of objects from the original lists.

Example:

myList[0] = new List<object>(){a, b, c, d};
myList[1] = new List<object>(){"0", "1", "2", "3", "4"};
myList[2] = new List<object>(){0, 1, 2};
myList[3] = new List<object>(){aClass, bClass}

etc.

Needs to become:

newList[0] =  new object[]{a, "0", 0, aClass};
newList[1] =  new object[]{a, "0", 0, bClass};
newList[2] =  new object[]{a, "0", 1, aClass};
newList[3] =  new object[]{a, "0", 1, bClass};
newList[4] =  new object[]{a, "0", 2, aClass};
newList[5] =  new object[]{a, "0", 2, bClass};
newList[6] =  new object[]{a, "1", 0, aClass};
newList[7] =  new object[]{a, "1", 0, bClass};
newList[8] =  new object[]{a, "1", 1, aClass};
newList[9] =  new object[]{a, "1", 1, bClass};
newList[10] = new object[]{a, "1", 2, aClass};
newList[11] = new object[]{a, "1", 2, bClass};

etc.

The order of the variables has to be preserved (the list at myList[0] has to be first, etc) because these object arrays are the parameters passed via reflection:

Indicator temp = (Indicator) newIndicator.Invoke(this, newList[i]);

If the number of lists of objects were static, it might look something like the following:

List<object[]> newList = new List<object[]>();
for(int i = 0; i < myList[0].Count; i++)
{
    for(int i2 = 0; i2 < myList[1].Count; i2++)
    {
        for(int i3 = 0; i3 < myList[2].Count; i3++)
        {
            for(int i4 = 0; i4 < myList[3].Count; i4++)
            {
                object[] temp = new object[]{myList[0][i], myList[1][i2], myList[2][i3], myList[3][i4]};
                newList.Add(temp);
            }
        }
    }
}

My latest attempt was to create a list of indicies which held the current index of each list and incremented it appropriately, but my math doesn't seem to work out as I scale it out.

        private List<object[]> ToParametersList(List<List<object>> listOfLists)
    {
        int counter = 1;
        foreach(List<object> list in listOfLists){ counter *= list.Count; }

        List<object[]> returnList = new List<object[]>();

        List<int> indicies = new List<int>();
        int tempSplit = 0;
        List<int> splits = new List<int>();
        List<int> splitcounters = new List<int>();
        for(int i = 0; i < listOfLists.Count; i++)
        {
            if(i == 0 && listOfLists[0].Count > 2)
            {
                splits.Add(counter / listOfLists[0].Count);
                tempSplit = counter / listOfLists[0].Count;
            } else if(i > 0 && listOfLists[i].Count > 2) {
                splits.Add(tempSplit / listOfLists[i].Count);
                tempSplit /= listOfLists[i].Count;
            } else if(listOfLists[i].Count == 2)
            {
                splits.Add(1);
            }
            indicies.Add(0);
            splitcounters.Add(1);
        }
        for(int i = 0; i < counter; i++)
        {
            object[] newObject = new object[listOfLists.Count];
            for(int i2 = 0; i2 < listOfLists.Count; i2++)
            {
                if(i < splits[i2] * splitcounters[i2] && ((indicies[i2] < listOfLists[i2].Count && listOfLists[i2].Count > 2) || indicies[i2] < listOfLists[i2].Count - 1))
                {
                    newObject[i2] = listOfLists[i2][indicies[i2]];
                }
                else if(i >= splits[i2] * splitcounters[i2] && ((indicies[i2] < listOfLists[i2].Count && listOfLists[i2].Count > 2) || indicies[i2] < listOfLists[i2].Count - 1))
                {
                    indicies[i2]++;
                    splitcounters[i2]++;
                    newObject[i2] = listOfLists[i2][indicies[i2]];
                }
                else
                {
                    indicies[i2] = 0;
                    splitcounters[i2]++;
                    newObject[i2] = listOfLists[i2][indicies[i2]];
                }
            }
            returnList.Add(newObject);
        }
        return returnList;
    }

I have also gone through many of the recursion questions on here and am still having trouble understanding how to apply them to this particular situation (I am relatively new to recursion).

Any help would be greatly appreciated!

EDIT: In Cartesian products with n number of list the OP's post is confusing and the answer provided has no explanation of what is happening. The link to Eric Lippert's Blog is a general overview of Cartesian products which did not help me break the barrier that I needed to properly understand this in the context of what I was trying to do.

Answer 1

To be honest i did not read your last attempt. Other ways using Linq is great but if you really want a recursion follow this way.

To create a good recursion you need to look at which part of method varies and which part does not. the method should take parameters that varies for each call. Also you need if-else to end recursion somewhere.

List<object[]> newList = new List<object[]>();
for(int i = 0; i < myList[0].Count; i++)
{
    for(int i2 = 0; i2 < myList[1].Count; i2++)
    {
        for(int i3 = 0; i3 < myList[2].Count; i3++)
        {
            for(int i4 = 0; i4 < myList[3].Count; i4++)
            {
                object[] temp = new object[]{myList[0][i], myList[1][i2], myList[2][i3], myList[3][i4]};
                newList.Add(temp);
            }
        }
    }
}

We want to use recursion in this method to be able to use it for any lenght of list.To do this you must convert loop into recursion call. but now you have unknown amount of loops.

The solution is to use params keyword. you can send any amount of int to method. this int's holds the variables i1, i2 , i3 , i4 .... just like the above method you have wrote.

The length of this array (params int[]) is exactly number of loops inside the normal method.

private static void Combine(List<List<object>> myList,List<object[]> newList,params int[] loopInd)
{
    if (loopInd.Length <= myList.Count) // should not exceed number of loops.
    {
        int currentCount = myList[loopInd.Length - 1].Count;

        while (loopInd[loopInd.Length - 1] < currentCount) // i<myList[0] , i2<myList[1] , i3<myList[2]
        {
            Combine(myList, newList, loopInd.Concat(new[] {0}).ToArray()); // Go for inner loop
            loopInd[loopInd.Length - 1]++; // i++, i2++ , i3++ ...
        }
    }
    else // no more loops.add the object[] into newList
    {
        int j = 0;
        object[] temp = loopInd.Take(loopInd.Length - 1).Select(i => myList[j++][i]).ToArray();
        newList.Add(temp);
    }
}

The comments above shows the representations in normal method.

Then you can use it in this way.

List<List<object>> myList = new List<List<object>>();
myList.Add(new List<object>() { a, b, c, d });
myList.Add(new List<object>() { "0", "1", "2", "3", "4" });
myList.Add(new List<object>() { 0, 1, 2 });
myList.Add(new List<object>() {aClass, bClass});

List<object[]> newList = new List<object[]>();

Combine(myList, newList, 0);

        // The newList is now what you want

Edit :

If you are after performance you can convert this Linq part

int j = 0;
object[] temp = loopInd.Take(loopInd.Length - 1).Select(i => myList[j++][i]).ToArray();
newList.Add(temp);

Into code

int j = 0;
object[] temp = new object[loopInd.Length - 1];

for (int i = 0; i < loopInd.Length - 1; i++,j++) 
{
    temp[i] = myList[j][loopInd[i]];
}

Answer 2

Here is a solution that accepts a number of lists that is unknown at compile time.
Method CombineArrayOfLists does what you need:

    static List<List<object>> CombineArrayOfLists(List<object>[] myList)
    {
        List<List<object>> result = myList[0].Select(element => new List<object>() { element }).ToList();

        for (int i = 1; i < myList.Length; i++)
        {
            result = (from c1 in result from c2 in myList[i] select new List<object>(c1) {c2}).ToList();
        }

        return result;
    }

Note that you need to define the desired behavior in case any list in your array of lists is empty. To handle that case you may need to add an if statement to skip that list (if that is the appropriate thing to do).

A complete example written in a slightly more verbose form that could be easier to understand:

class Program
{
    static void Main(string[] args)
    {
        List<object>[] myList = new List<object>[4];

        AClass aClass = new AClass();
        BClass bClass = new BClass();

        myList[0] = new List<object>() { "a", "b", "c", "d" };
        myList[1] = new List<object>() { "0", "1", "2", "3", "4" };
        myList[2] = new List<object>() { 0, 1, 2 };
        myList[3] = new List<object>() { aClass, bClass };

        List<List<object>> result = CombineArrayOfLists(myList);

        PrintList(result);
    }

    static List<List<object>> CombineArrayOfLists(List<object>[] myList)
    {
        List<List<object>> result = myList[0].Select(element => new List<object>() { element }).ToList();

        for (int i = 1; i < myList.Length; i++)
        {
            result = CombineCollections(result, myList[i]).ToList();
        }

        return result;
    }

    private static IEnumerable<List<object>> CombineCollections(IEnumerable<List<object>> collection1, List<object> collection2)
    {
        return from c1 in collection1 from c2 in collection2 select new List<object>(c1) { c2 };
    }

    // A more verbose form of CombineCollections that may be easier to understand:
    //private static IEnumerable<List<object>> CombineCollections(IEnumerable<List<object>> collection1, List<object> collection2)
    //{
    //    foreach (List<object> c1 in collection1)
    //    {
    //        foreach (object c2 in collection2)
    //        {
    //            List<object> l1 = new List<object>(c1) { c2 };
    //            yield return l1;
    //        }
    //    }
    //}

    private static void PrintList(List<List<object>> collection)
    {
        collection.ForEach(list =>
        {
            list.ForEach(element =>
            {
                Console.Write(element);
                Console.Write(" ");
            });

            Console.WriteLine();
        });
    }
}

public class AClass
{ }

public class BClass
{ }

Answer 3

You can use LINQ to get Cartesian product of list of objects.

List<object> arr1 = new List<object> { "a", "b", "c" };
            List<object> arr2 = new List<object> { 3, 2, 4,5 };
            List<object> arr3 = new List<object> { "0", "1", "2", "3", "4" };


            var result = from x in arr1
                         from y in arr2
                         from z in arr3
                         select new { x = x, y = y,z=z };

            List<object[]> newList = new List<object[]>();

            foreach (var line in result)
            {
                newList.Add(new object[] { line.x, line.y, line.z });                     
            }

            foreach (var obj in newList)
            {
                foreach (var ele in obj)
                {
                    Console.Write(ele.ToString() + " ");
                }
                Console.WriteLine();
            }
            Console.ReadKey();

This will provide you with the list of one objects in the way you require.

Here is the running example http://csharppad.com/gist/45ebe7c9576dab9c00b8