Using Permutation for Better Testing in .Net

9/7/2010

I've been working on a number of products lately, although most of them I'm not really able to talk about at the moment. The one thing that I can talk about is a side project though. For the last couple of weeks, I've been working on ways to improve my testing techniques. I do unit tests, do continuous builds/testing, I test the extremes, use randomly generated inputs, etc. But I've been finding that those techniques really aren't finding the bugs in my code lately. I've found that most of my bugs tend to be found in integration testing.

For example, if I have functions A, B, C, and D and call them in that order, it works. However what happens if I call B before A? Or C before B? Most people never test this in unit testing, nor in most cases would you want to. With 3 or 4 functions the number of possible permutations is low (6 and 24 respectively), but it grows rather quickly as just having 5 functions increases the number of permutations to 120. I don't know about you, but I don't want to write that much code. However with a bit of effort we can automate that for us. All we need is one function call to generate all of those permutations for us (well and the function itself):

   1: public static class Permutation
   2:  
   3: {
   4:  
   5:     #region Public Static Functions
   6:  
   7:  
   8:  
   9:     /// <summary>
  10:  
  11:     /// Finds all permutations of the items within the list
  12:  
  13:     /// </summary>
  14:  
  15:     /// <typeparam name="T">Object type in the list</typeparam>
  16:  
  17:     /// <param name="Input">Input list</param>
  18:  
  19:     /// <returns>The list of permutations</returns>
  20:  
  21:     public static List<List<T>> Permute<T>(List<T> Input)
  22:  
  23:     {
  24:  
  25:         List<T> Current=new List<T>();
  26:  
  27:         Current.AddRange(Input);
  28:  
  29:         List<List<T>> ReturnValue = new List<List<T>>();
  30:  
  31:         int Max = MathHelper.Factorial(Input.Count - 1);
  32:  
  33:         for (int x = 0; x < Input.Count; ++x)
  34:  
  35:         {
  36:  
  37:             int z = 0;
  38:  
  39:             while (z < Max)
  40:  
  41:             {
  42:  
  43:                 int y = Input.Count - 1;
  44:  
  45:                 while (y > 1)
  46:  
  47:                 {
  48:  
  49:                     T TempHolder = Current[y - 1];
  50:  
  51:                     Current[y - 1] = Current[y];
  52:  
  53:                     Current[y] = TempHolder;
  54:  
  55:                     --y;
  56:  
  57:                     List<T> TempList = new List<T>();
  58:  
  59:                     TempList.AddRange(Current);
  60:  
  61:                     ReturnValue.Add(TempList);
  62:  
  63:                     ++z;
  64:  
  65:                     if (z == Max)
  66:  
  67:                         break;
  68:  
  69:                 }
  70:  
  71:             }
  72:  
  73:             if (x + 1 != Input.Count)
  74:  
  75:             {
  76:  
  77:                 Current.Clear();
  78:  
  79:                 Current.AddRange(Input);
  80:  
  81:                 T TempHolder2 = Current[0];
  82:  
  83:                 Current[0] = Current[x + 1];
  84:  
  85:                 Current[x + 1] = TempHolder2;
  86:  
  87:             }
  88:  
  89:         }
  90:  
  91:         return ReturnValue;
  92:  
  93:     }
  94:  
  95:  
  96:  
  97:     #endregion
  98:  
  99: }

This function call creates a list to hold all the permutations (which are themselves a list of items). It then finds the factorial of the number of items that we sent in minus 1 (the actual number of permutations will be the factorial of the number of items we sent in, but we need this number for our inner loop). The function is then broken down into an inner loop and an outer loop. The inner loop takes the item at the back, moves it to the left, and then creates a new permutation. It then keeps moving it to the left until it's at the second item slot (index of 1), each time creating a new permutation. Once the item is in the second item slot, it goes to the back of the list and starts the process over again. This is done until we hit the factorial that we calculated earlier (once it does reach this point it kicks us to the outer portion of the loop). At this point we simply switch the first item and second item in the original list (each time we reach this point we switch the next item and the first) and then start over. And once it's done, we just return the permutation list.

I made this function call generic so it can be used for a number of things (name generators, etc.). But in our case we're worried about function calls. Thankfully this is rather simple thanks to classes like Func. The Func class is a generic type that encapsulates a function call. And since a Func instance is an object, we can send them into the function and get our permutations. Let's assume we have the following class (it's crap, but I'm just using it as an example):

   1: public static class TempClass
   2:  
   3: {
   4:  
   5:     public static string Temp(int Val)
   6:  
   7:     {
   8:  
   9:         return "Function1";
  10:  
  11:     }
  12:  
  13:  
  14:  
  15:     public static string Temp2(int Val)
  16:  
  17:     {
  18:  
  19:         return "Function2";
  20:  
  21:     }
  22:  
  23:  
  24:  
  25:     public static string Temp3(int Val)
  26:  
  27:     {
  28:  
  29:         return "Function3";
  30:  
  31:     }
  32:  
  33: }

We can get the permutations for these functions by doing the following:

   1: List<Func<int, string>> FunctionCalls=new List<Func<int,string>>();
   2:  
   3: FunctionCalls.Add(TempClass.Temp);
   4:  
   5: FunctionCalls.Add(TempClass.Temp2);
   6:  
   7: FunctionCalls.Add(TempClass.Temp3);
   8:  
   9: List<List<Func<int, string>>> Calls = Utilities.Math.Permutation.Permute<Func<int, string>>(FunctionCalls);

Calls would end up containing 6 different permutations of those three functions, which we could then call during our testing. Now in the example above the functions have the same number/type of parameters and return types, but you could easily wrap the Func class to handle different function calls. In fact in cases where 2+ function calls have to be called in a specific order, you could have the wrapper class hold multiple Func calls. But that gets into later posts that I'll be making. For now, test out the code, leave feedback, and happy coding.



Comments