Permutations and missing values, helpful with unit testing

by Alex Siepman 13. January 2014 15:41

Creating of unit tests of a method with 1 bool parameter needs at least 2 unit tests (false and true). But how many unit tests do you need for a parameter of type IEnumerable<int>? A variant of the Permutations() method will help you to create almost all necessary combinations with just one extension method!

Imagine you want to test this horrible method to find the smallest value:

public static int MinValue(IEnumerable<int> items)
{
    // Not tested for items is null or empty
    var result = items.ElementAt(0);
    for (int i = 1; i < items.Count(); i++)
    {
        if (items.ElementAt(i) < items.ElementAt(i - 1))
        {
            result = items.ElementAt(i);
            break;  // Quit before all items are checked
        }
    }
    return result;
}

Although the method is not correct implemented, the method passes the following unit test.

[TestMethod]
public void MinMinValueTest()
{
    var targets = new[]
    {
        new []{1},
        new []{1,2},
        new []{2,1},
        new []{1,3},
        new []{3,1},
        new []{1,2,3},
        new []{2,1,3},
        new []{2,3,1},
        new []{3,1,2},
    };
    Assert.IsTrue(targets.All(t => t.MinValue() == 1));
}

Only 9 combinations are tested. But if other combinations would also be added, the test woud not pass.

Permutations

Testing all permutations of 123 would be better. It would result in these combinations:

123
132
213
231
312
321

Creating all permutations can be implemented this way:

public static IEnumerable<IEnumerable<T>> Permutations<T>(this IEnumerable<T> source)
{
    if (source == null)
    {
        throw new ArgumentNullException("source");
    }
    return source.PermutationsImplementation();
}

private static IEnumerable<IEnumerable<T>> PermutationsImplementation<T>(this IEnumerable<T> source)
{
    var sourceCache = source.ToList(); // ToList() makes it about twice as fast
    if (sourceCache.IsSingle())
    {
        return sourceCache.ToIEnumerable();
    }
    return sourceCache
        .Select((a, index1) => PermutationsImplementation(sourceCache.Where((b, index2) => index2 != index1))
        .Select(b => a.PrependImplementation(b)))
        .SelectMany(c => c);
}

and using this method for Prepend (or Prepend Implementation, without any checks):

public static IEnumerable<TSource> Prepend<TSource>(
    this TSource item,
    IEnumerable<TSource> items)
{
    if (items == null)
    {
        throw new ArgumentNullException("items");
    }
    return PrependImplementation(item, items);
}

private static IEnumerable<TSource> PrependImplementation<TSource>(
    this TSource item,
    IEnumerable<TSource> items)
{
    yield return item;
    foreach (var item2 in items)
    {
        yield return item2;
    }
}

To prevent unnecessary creations of arrays (new [] {1}) when Implementing IEnumerable for 1 item. I used this method:

public static IEnumerable<TSource> ToIEnumerable<TSource>(this TSource item)
{
    yield return item;
}

You can use the IsSingle() implementation of my previous post or this implementation:

public static bool IsSingle<T>(this IEnumerable<T> source)
{
    using (IEnumerator<T> enumerator = source.GetEnumerator())
    {
        return enumerator.MoveNext() && !enumerator.MoveNext();
    }
}

Permutatons with missing values

An even better option would be to test wit all permutations with "missing values".

1
2
3
12
21
13
31
23
32
123
132
213
231
312
321

I will show you step by step how I created that list.

First, create a list with all bool combinations (F = False, T = true):

FFF
FFT
FTF
FTT
TFF
TFT
TTF
TTT

Done with this method:

public static IEnumerable<IEnumerable<bool>> AllBooleansCombinations(int count)
{
    if (count <= 0)
    {
        return Enumerable.Empty<IEnumerable<bool>>();
    }
    if (count == 1)
    {
        return OneBooleanCombination();
    }
    var result = AllBooleansCombinations(count - 1).Select(c => false.Prepend(c))
                    .Concat(
                    AllBooleansCombinations(count - 1).Select(c => true.Prepend(c)));
    return result;
}

private static IEnumerable<IEnumerable<bool>> OneBooleanCombination()
{
    yield return false.ToIEnumerable();
    yield return true.ToIEnumerable();
}

Second, for al items in that list: remove the false positions I.e.: 123 and TFT becomes 13. The you get this list:

1
2
3
12
13
23
123

Done with this method:

public static IEnumerable<IEnumerable<T>> WithMissingItems<T>(this IEnumerable<T> source, bool orderItems = true)
{
    if (source == null)
    {
        throw new ArgumentNullException("source");
    }
    T[] sourceArray = source.ToArray();
    var booleansCombinations = AllBooleansCombinations(sourceArray.Length);
    var result = booleansCombinations.Select(b => FilterItems(b, sourceArray));
    if (orderItems)
    {
        result = result.Reverse().OrderBy(c => c.Count());
    }
    return result;
}

private static IEnumerable<T> FilterItems<T>(this IEnumerable<bool> booleans, T[] items)
{
    var zippedCombinations = booleans.Zip(items, (boolean, item) => new { boolean, item });
    return zippedCombinations.Where(z => z.boolean).Select(z => z.item);
}

At this point it is easy. Just create permutations for all items in the list above and you have the final result:

public static IEnumerable<IEnumerable<T>> PermutationsWithMissingItems<T>(
    this IEnumerable<T> source)
{
    if (source == null)
    {
        throw new ArgumentNullException("source");
    }
    var withMissingItems = source.WithMissingItems();
    return withMissingItems.SelectMany(m => m.Permutations());
}

Unit testing al combinations, the easy way

Image we would unit test the following LINQ min() extension method:

public static TSource Min<TSource>(this IEnumerable<TSource> source)
{
    // Implementation not provided
}

This can now be tested with a test for null, empty and this unit test to test al 15 combinations of 123 inclusing missing items:

[TestMethod]
public void MinTest()
{
    var targets = new[] { 1, 2, 3 }.PermutationsWithMissingItems();
    Assert.IsTrue(targets.All(t => t.Min() == 1));
}

How fast is it?

Unit test are only run often if it is not to slow. This code:

new[] { 1,  2, 3 , 4, 5, 6, 7, 8}.PermutationsWithMissingItems().Last();

created 109600 lists of items. On a simple computer with an I5 processor it took only 0.2 seconds.

And this code to iterate all items of all lists:

new[] { 1,  2, 3 , 4, 5, 6, 7, 8}.permutationsWithMissingItems.SelectMany(i => i).Last()

created 767208 items. It took only 0.45 seconds.

Usually 123, 12345 or 112233 (and Distict) will be enough.

Add comment

  Country flag

biuquote
  • Comment
  • Preview
Loading

About the author

I am a software architect at Roxit and also a C# Developer. My main interests in the area of ​​C# are LINQ and generics

Visit my personal homepage (Dutch) for more info about me.

Month List

Page List