Unknown number for loops using recursion

Question

I did some research before and found some great articles, but I can't come up with any solutions for this problem. From my research, I believe that using recursion would be the best way to solve this problem. I made an example using some common classes, but essentially my problem: I have about 10 classes that I can have on the list. I can only have one of these classes, and I can have all ten. Ultimately, I find the best combination of “items” (which everyone inherits from the element) for this problem. I think it will be pretty easy, except that I have to deal with creating combinations before each test.

The following is sample code using only two classes. If recursion is not the best way to approach this problem, please correct it as necessary. How can I convert this to be used for any number of elements that are needed for testing with?

Edited: as some of them indicated that my sample code is an iterative solution, but this is only useful if I have two elements. Therefore, I need to define a recursive function to solve the problem based on the number of loops needed at runtime.

-Chance

Research:

C #: N for loops

Arbitrary number of nested loops?

The 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

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

Using:

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

Answer 2

I think the following should work.

To do this, you need to create a stack of types of elements that you want to test, and a stack from each of those present in the source list, and two stacks are synchronized with each other.

The Input List parameter must be empty.

 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 does not list / test lists that do not contain at least one of each element type.

Second Note: Now this includes missing cases. It will also check the empty list.

Answer 3

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

EXAMPLE: myItem = Item1 Item1 Item2 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 that the above code was written inside the browser window and not verified, so syntax errors may occur.