快速判断List<List<T>>类型数据结构相等性的算法需求

问题背景 #

需要判断两个List<List<T>>是否包含完全相同的数据，规则如下：

• T是可直接用==判断相等的原始类型（如int、float）；
• 内层List<T>是有序的操作序列，元素顺序必须完全一致才视为相等；
• 外层List<List<T>>是无序的操作集合，仅需判断元素是否存在，顺序不影响相等性。

示例 #

List<int> l1 = new() {1, 2, 3};
List<int> l2 = new() {5, 6, 7, 8};
List<int> l3 = new() {3, 1, 2}; // 元素和l1相同但顺序不同

List<List<int>> LL1 = new() {l1, l2};
List<List<int>> LL2 = new() {l2, l1};
List<List<int>> LL3 = new() {l2, l3};

预期结果：LL1与LL2相等；LL1、LL2都和LL3不相等。

当前解法 #

现有实现代码如下：

bool CheckEqual(List<List<T>> l1, List<List<T>> l2)
{
    if(l1.Count != l2.Count) return false;
    for (int i = 0; i < l1.Count; i++)
    {
        List<T> operation1 = l1[i];
        for (int j = 0; j < l2.Count; j++)
        {
             List<T> operation2 = l2[j];
             if(operation1.SequenceEqual(operation2))
             {
                  l1.RemoveAt(i);
                  l2.RemoveAt(j);
                  break;
             }
        }
    }
    return l1.Count == 0 && l2.Count == 0;
}

注：内层List<T>的元素数量最多可达10000个，外层List<List<T>>的元素数量最多为20-30个。

当前解法的问题 #

1. 修改原集合：直接对传入的l1和l2执行RemoveAt操作，会破坏调用者的原始数据，属于意料之外的副作用；
2. 性能浪费：嵌套循环中多次重复调用SequenceEqual（内层列表最长10000元素，每次比较都是O(K)开销），加上RemoveAt是O(N)的数组移动操作，整体效率不高；
3. 逻辑漏洞：循环中i的递增会因为RemoveAt导致索引错乱，比如移除第i个元素后，下一个元素会移到i位置，但循环会直接i++，导致跳过该元素。

优化方案 #

方案1：哈希表统计频次 #

核心思路是给每个有序子列表生成唯一哈希标识，统计每个标识的出现次数，最终比较两个集合的频次是否完全一致。

bool CheckEqual<T>(List<List<T>> l1, List<List<T>> l2) where T : struct, IEquatable<T>
{
    if (l1.Count != l2.Count)
        return false;

    // 自定义子列表相等比较器，判断顺序是否完全一致
    var listEqualityComparer = new ListEqualityComparer<T>();
    var countDict = new Dictionary<List<T>, int>(listEqualityComparer);

    // 统计第一个集合的子列表频次
    foreach (var list in l1)
    {
        countDict.TryGetValue(list, out int count);
        countDict[list] = count + 1;
    }

    // 用第二个集合抵消频次，发现不匹配直接返回false
    foreach (var list in l2)
    {
        if (!countDict.TryGetValue(list, out int count) || count == 0)
            return false;
        countDict[list] = count - 1;
    }

    // 所有频次都归零则相等
    return countDict.Values.All(v => v == 0);
}

// 自定义List<T>的相等比较器，支持哈希计算和顺序相等判断
public class ListEqualityComparer<T> : IEqualityComparer<List<T>> where T : IEquatable<T>
{
    public bool Equals(List<T>? x, List<T>? y)
    {
        if (ReferenceEquals(x, y)) return true;
        if (x == null || y == null) return false;
        return x.SequenceEqual(y);
    }

    public int GetHashCode(List<T> obj)
    {
        if (obj == null) return 0;
        int hash = 17; // 初始哈希值
        foreach (var item in obj)
        {
            hash = hash * 31 + item.GetHashCode(); // 31是质数，减少哈希冲突
        }
        return hash;
    }
}

方案2：排序后逐次比较 #

先对两个外层集合排序（排序时依据子列表的顺序内容），再逐个比较对应位置的子列表是否相等。

bool CheckEqual<T>(List<List<T>> l1, List<List<T>> l2) where T : struct, IComparable<T>, IEquatable<T>
{
    if (l1.Count != l2.Count)
        return false;

    // 复制原集合，避免修改原始数据
    var sortedList1 = new List<List<T>>(l1);
    var sortedList2 = new List<List<T>>(l2);

    // 自定义排序规则：先比长度，再逐个元素比顺序
    sortedList1.Sort((a, b) =>
    {
        if (a.Count != b.Count)
            return a.Count.CompareTo(b.Count);
        for (int i = 0; i < a.Count; i++)
        {
            int cmp = a[i].CompareTo(b[i]);
            if (cmp != 0)
                return cmp;
        }
        return 0;
    });

    sortedList2.Sort((a, b) =>
    {
        if (a.Count != b.Count)
            return a.Count.CompareTo(b.Count);
        for (int i = 0; i < a.Count; i++)
        {
            int cmp = a[i].CompareTo(b[i]);
            if (cmp != 0)
                return cmp;
        }
        return 0;
    });

    // 逐个比较排序后的子列表
    for (int i = 0; i < sortedList1.Count; i++)
    {
        if (!sortedList1[i].SequenceEqual(sortedList2[i]))
            return false;
    }

    return true;
}

方案选择 #

• 如果外层集合元素数量较多（比如超过100个），优先选哈希表方案，时间复杂度更低；
• 对于外层只有20-30个元素的场景，排序方案实现更直观，性能差异可以忽略；
• 两种方案都避免了修改原集合的问题，且减少了重复的子列表比较次数。

内容的提问来源于stack exchange，提问作者Aditya