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

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 2

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