Unknown number for loops using Recursion

Question

I have done some research prior to and have found some great articles but I can't seem to tailor any of the solutions for my given problem. From the research done, I believe the best method of going about this problem would be to use recursion. I have made an example using some generic classes but essentially my problem is I have approximately 10 classes that I can have in a list. I might have only one of these classes and I might have all ten. I am ultimately finding the best combination of "items" (which all inherit from item) for a given problem. I think this would be fairly easy except for I have to deal with creating the combinations before each test.

Below is some sample code using only two classes. If recursion is not the best way to approach this problem then please correct as needed. How might I convert this to be used for any number of items that are needed to test with?

Edited: As some have pointed out my example code is the iterative solution however it is only useful if I have two items. Therefore, I need to define a recursive function to solve the problem based upon the number of for loops needed upon runtime.

-Chance

Research:

C#: N For Loops

Arbitrary number of nested-loops?

Number of nested loops at runtime

static void Main(string[] args)
    {
        List<Item> myItem = new List<Item>();

        int numberItem1 = 0, numberItem2 = 0;
        foreach (var item in myItem)
        {
            if (item.GetType() == typeof(Item1))
            {
                numberItem1++;
            }
            else if (item.GetType() == typeof(Item2))
            {
                numberItem2++;
            }
        }

        List<Item> testingItems = new List<Item>();
        //FirstItem
        for (int a = 0; a < numberItem1; a++)
        {
            for (int b = 0; b <= a; b++)
            {
                testingItems.Add(new Item1 { });                
            }
            //DoTest()

            testingItems.Clear();
            //Second Item
            for (int c = 0; c < numberItem2; c++)
            {
                for (int d = 0; d <= a ; d++)
                {
                    testingItems.Add(new Item1 { });
                }
                for (int e = 0; e <= c; e++)
                {
                    testingItems.Add(new Item2 { });
                }
                //DoTest()
                testingItems.Clear();
            }
        }
    }

Answer 1

I think the following should work.

This requires you to build a stack of the item types you want to test, and a stack of the number of each present in the original list, with the two stacks in sync with each other.

The input List parameter should be an empty list.

void RecursiveTest(List<Item> testingItems, Stack<Type> itemTypes, Stack<int> itemCounts)
{
    if (itemTypes.Count == 0) { return; }
    Type thisType = itemTypes.Pop();
    int thisCount = itemCounts.Pop();
    List<Item> addedItems = new List<Item>();
    for (int i = 0; i <= thisCount; i++)
    {
        if (i > 0)
        {
            Item thisItem = (Item)Activator.CreateInstance(thisType);
            testingItems.Add(thisItem);
            addedItems.Add(thisItem);
        }

        if (itemTypes.Count == 0)
        {
            DoTest(testingItems);
        }
        else
        {
            RecursiveTest(testingItems, itemTypes, itemCounts);
        }
    }
    foreach(Item addedItem in addedItems)
    {
        testingItems.Remove(addedItem);
    }
    itemTypes.Push(thisType);
    itemCounts.Push(thisCount);
}

Note: This code doesn't output/test lists that don't contain at least one of each item type.

Second note: This now includes the missing cases. It will, however, also test the empty list.

Answer 2

EDIT
This code should generate all the possible test permutations for the list of items + the maximum number of each item that should appear in each test.

EXAMPLE: myItem = Item1 Item1 Item2 Item2 Item3 tests = 1,0,0; 2,0,0; 0,1,0; 1,1,0; 2,1,0; 0,2,0; 1,2,0; 2,2,0; 0,0,1; 1,0,1; 2,0,1; 0,1,1; 1,1,1; 2,1,1; 0,2,1; 1,2,1; 2,2,1

List<Item> myItem = new List<Item>();
List<Type> myOrder = new List<Item>();
Dictionary<Type, int> myCount = new Dictionary<Type, int>();
foreach (var item in myItem)
{
 if (myCount.ContainsKey(item.GetType()))
 {
  myCount[item.GetType()]++;
 }
 else
 {
  myOrder.Add(item.GetType());
  myCount.Add(item.GetType(), 1);
 }
}

List<Item> testingItems = new List<Item>();
int[] testingCounts = new int[myCount.Count];
while(IncrementCounts(testingCounts, myOrder, myCount)) {
 for(int x=0; x<testingCounts.length; x++) {
  AddInstances( testingItems, myOrder[x], testingCounts[x] );
 }
 // doTest()
 testingItems.Clear();
}

// count permutations using the maxima
// EXAMPLE: maxima [2, 2, 2]
//  1,0,0; 2,0,0; 0,1,0; 1,1,0; 2,1,0; 0,2,0; 1,2,0; 2,2,0; 0,0,1; 1,0,1; 2,0,1 etc..
public static bool IncrementCounts(int[] counts, List<Type> order, Dictionary<Type, int> maxima) {
 for(int x=0; x<counts.length; x++) {
  if(counts[x] + 1 <= maxima[order[x]]) {
   counts[x]++;
   return true;
  } else {
   counts[x] = 0;
  }
 }
 return false; // overflow, so we're finished
}     

public static void AddIstances(List<Item> list, Type type, int count) {
 for(int x=0; x<count; x++) {
  list.Add( Convert.ChangeType( Activator.CreateInstance(type), type ) );
 }
}

Please note the above code was written inside the browser window and is untested, so syntax errors may exist.

Answer 3

Non-recursive solution.

IEnumerable<List<Item>> TestLists(List<Item> fullList)
{
    List<Type> types = fullList.Select(i => i.GetType()).Distinct().ToList();
    List<Item> testList = new List<Item> { (Item)Activator.CreateInstance(types[0]) };
    yield return testList;

    bool finished = false;
    while (!finished)
    {
        bool incremented = false;
        int i = 0;
        while (i < types.Count && !incremented)
        {
            if (testList.Where(t => t.GetType() == types[i]).Count() <
                fullList.Where(t => t.GetType() == types[i]).Count())
            {
                testList.Add((Item)Activator.CreateInstance(types[i]));
                incremented = true;
            }
            else
            {
                testList = testList.Where(t => t.GetType() != types[i]).ToList();
                i++;
            }
        }
        if (incremented)
        {
            yield return testList;
        }
        else
        {
            finished = true;
        }
    }
}

Usage:

foreach (var partList in TestLists(myListToTest))
{
    DoTest(partList);
}