Asserting two List<List<T>> Are Equivalent to Each Other

Question

To make sure that two lists are the same, in nunit, we can use CollectionAssert.AreEquivalent to check that these two lists contain the same elements ( orders not important).

But how to check whether two List<List<T>> are equivalent? The idea is that if one List<T> has the same elements as the other List<T> ( again, order not important) then they are equal.

Answer 1

I don't think you get around checking for each element individually. I'll typically first check for equal length, then loop for say i over the lists' length and check that list1[i]==list2[i]

update

Sorry, missed the (central) part about elements not having to be in order. In that case, create a HashSet with the elements of the second list and check for each element in list1 if it's in the hashset. This reduces the running time for the lookup from linear to logarithmic.

update 2 As noted by Donald Ray, you have to check both ways if you have possible multiple occurrences of single objects in any of the lists.

Answer 2

You do have to loop through them to be sure that they are equivalent, but with some important shortcuts:

1. If they are actually the same instance (and in real code this often comes up), then ReferenceEquals(x, y) will return true. Otherwise it won't. If ReferenceEquals returns true, then they are equivalent.

2. If one is null and the other isn't, then obviously they aren't equal (if they are both null you'll have caught that above with ReferenceEquals). You'll need to test for null anyway for safety, so you've another short-cut in many cases.

3. If they are of different sizes then (for most definitions of equivalence, there are exceptions) they are not equal. Return false immediately.

4. The moment you've found a mismatch, you can return false without continuing to check.

5. It will be faster to compare them if they are already sorted. If you can keep them sorted, or failing that keep track of whether they are sorted or not and then sort only when needed, you can massively speed things up. (Note though that many sorting algorithms have their worse-case behaviour when needlessly sorting a list that is already sorted).

Answer 3

I think you will need to write your own code to do this.

Look at how CollectionAssert.AreEquivalent works with Reflector then write your own helper class "MyAsserts".

You will have to be clever if you wish to run faster than O(n^2*m^2) where n is the number of lists in the outmost list and m is the number of items in the inner lists.

The simple solution is to loop over all “inner lists” in the list1 and use the code from CollectionAssert.AreEquivalent to check if list2 contains such a list. Then swap list1 and list2 and repeat. However you can do a lot better.

(You then need to work out how to produce a helpful message when the lists are not equivalent.)

Answer 4

Here's an attempt, not tested. If each inner list contains m elements, and the outer list-list contains n lists, I believe the complexity is O (n^2 x m), but I might be wrong. Assumptions:

1. T does not implement IComparable or any such interface that allows sorting.
2. Ordering is irrelevant to equality for both the List<List<T>>s and the composing List<T> objects.

--

public static bool ListListsAreEqual<T>(List<List<T>> listlist1, List<List<T>> listlist2)
{
    if (listlist1.Count != listlist2.Count)
        return false;

    var listList2Clone = listlist2.ToList();

    foreach (var list1 in listlist1)
    {
        var indexOfMatchInList2 = listList2Clone
                   .FindIndex(list2 => ListsArePermutations(list1, list2));

        if (indexOfMatchInList2 == -1)
            return false;

        listList2Clone.RemoveAt(indexOfMatchInList2);
    }

    return true;
}

private static bool ListsArePermutations<T>(List<T> list1, List<T> list2)
{
    return list1.Count == list2.Count && new HashSet<T>(list1).SetEquals(list2);
}

Answer 5

I'd use SelectMany() and flatten the list. Now you can either compare element against element, using Assert.Equals() or use a normal collection assert for lists. A query expression with two from clauses will do the same thing:

void AssertEquals<T>(List<List<T>> expected, List<List<T>> actual)
{
  var flatExpected = expected.SelectMany(x=>x);
  var flatActual = expected.SelectMany(x=>x);

  CollectionAssert.Equals(flatExpected, flatActual);
}

Note that this is a very naive implementation only, the flattened sequences may be equal while the source sequences contain the same elements but in a different partitioning.