Asserting two List> Are Equivalent to Each Other

Вот попытка, не проверенная. Если каждый внутренний список содержит m элементов, а внешний список-список содержит n списков, я считаю, что сложность составляет O (n ^ 2 xm) , но Я могу быть не прав. Предположения:

1. T не реализует IComparable или какой-либо другой интерфейс, который позволяет сортировку.
2. Порядок не имеет отношения к равенству как для объектов List > , так и для составляющих объектов List .

-

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

Я думаю, вам нужно будет написать свой собственный код для этого.

Посмотрите, как CollectionAssert.AreEquivalent работает с Reflector, затем напишите свой собственный вспомогательный класс MyAsserts.

Вам нужно проявить смекалку, если вы хотите бежать быстрее, чем O (n ^ 2 * m ^ 2), где n - количество списков в крайнем списке, а m ] - количество элементов во внутренних списках.

Простое решение - перебрать все «внутренние списки» в list1 и использовать код из CollectionAssert.AreEquivalent, чтобы проверить, содержит ли list2 такой список. Затем поменяйте местами list1 и list2 и повторите. Однако вы можете сделать намного лучше.

(Затем вам нужно решить, как составить полезное сообщение, когда списки не эквивалентны.)

Вы должны просмотреть их в цикле, чтобы убедиться, что они эквивалентны, но с некоторыми важными сокращениями:

1. Если они на самом деле являются одним и тем же экземпляром (а в реальном коде это часто возникает ), то ReferenceEquals (x, y) вернет истину. Иначе не будет. Если ReferenceEquals возвращает истину, то они эквивалентны.

2. Если один из них равен нулю, а другой нет, то очевидно, что они не равны (если они оба равны нулю, вы поймете это выше с помощью ReferenceEquals ). В любом случае вам нужно будет протестировать на null для безопасности, так что во многих случаях у вас есть еще один короткий путь.

3. Если они разного размера, то (для большинства определений эквивалентности бывают исключения) они не равны. Немедленно вернуть false.

4. В тот момент, когда вы обнаружите несоответствие, вы можете вернуть false, не продолжая проверку.

5. Их будет быстрее сравнить, если они уже отсортированы. Если вы можете держать их отсортированными или, если это не удается, отслеживать, отсортированы они или нет, а затем сортировать только при необходимости, вы можете значительно ускорить процесс. (Обратите внимание, что многие алгоритмы сортировки имеют худшее поведение при бесполезной сортировке уже отсортированного списка).

Я бы использовал SelectMany () и сгладил список. Теперь вы можете либо сравнить элемент с элементом, используя Assert.Equals (), либо использовать обычное утверждение коллекции для списков. Выражение запроса с двумя предложениями from будет делать то же самое:

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

Обратите внимание, что это только очень наивная реализация, уплощенные последовательности могут быть равны, в то время как исходные последовательности содержат те же элементы, но в другом разделении.

Я не думаю, что вам придется проверять каждый элемент в отдельности. Обычно я сначала проверяю равную длину, затем повторяю цикл, скажем, i по длине списков, и проверяю, что list1 [i] == list2 [i]

update

Извините, я пропустил (центральную) часть об элементах не обязательно быть в порядке. В этом случае создайте HashSet с элементами второго списка и проверьте каждый элемент в list1, если он находится в хэш-наборе. Это сокращает время выполнения поиска с линейного до логарифмического.

обновление 2 Как отметил Дональд Рэй, вы должны проверить оба способа, если в любом из списков возможно несколько вхождений одного объекта.