c# - 如何使用 UNION 对字符/字符串数组进行分组？

Question

我有一个二维的 char 数组，叫做 Letters[ ][ ]

Letters[0][0] = A
       [0][1] = B

Letters[1][0] = C
       [1][1] = D

Letters[2][0] = B
       [2][1] = A
       [2][2] = F

Letters[3][0] = I
       [3][1] = F
       [3][2] = J

我需要把它分组，所以它会是这样的:

group[0] [0] = A
group[0] [1] = B
group[0] [2] = F
group[0] [3] = I
group[0] [4] = J

group[1] [0] = C
group[1] [1] = D

到目前为止，对于我的问题，我的逻辑是检查每个元素与其他元素。如果两个元素都是相同的字母，它将与整个其他数组元素组合在一起，没有双重/重复元素。但是，我不确定是使用 C# Linq Union 还是仅使用标准数组访问。

我应该如何以最佳方式对其进行分组？或者还有其他解决方案吗？

Answer 1

我认为纯 LINQ 解决方案过于复杂。这不是(如果我正确理解您的规范)一个简单的联合操作。您想要基于非空交集进行合并。这意味着必须首先重新排列数据，以便 LINQ 可以进行连接，以找到匹配的数据，并且由于 LINQ 只会在相等的情况下连接，因此在保留原始分组信息的同时这样做将导致语法更麻烦多于它的值(value)，恕我直言。

这是一种适用于您给出的示例的非 LINQ 方法:

static void Main(string[] args)
{
    char[][] letters =
    {
        new [] { 'A', 'B' },
        new [] { 'C', 'D' },
        new [] { 'B', 'A', 'F' },
        new [] { 'I', 'F', 'J' },
    };

    List<HashSet<char>> sets = new List<HashSet<char>>();

    foreach (char[] row in letters)
    {
        List<int> setIndexes = Enumerable.Range(0, sets.Count)
        .Where(i => row.Any(ch => sets[i].Contains(ch))).ToList();

        CoalesceSets(sets, row, setIndexes);
    }

    foreach (HashSet<char> set in sets)
    {
        Console.WriteLine("{ " + string.Join(", ", set) + " }");
    }
}

private static void CoalesceSets(List<HashSet<char>> sets, char[] row, List<int> setIndexes)
{
    if (setIndexes.Count == 0)
    {
        sets.Add(new HashSet<char>(row));
    }
    else
    {
        HashSet<char> targetSet = sets[setIndexes[0]];

        targetSet.UnionWith(row);

        for (int i = setIndexes.Count - 1; i >= 1; i--)
        {
            targetSet.UnionWith(sets[setIndexes[i]]);
            sets.RemoveAt(setIndexes[i]);
        }
    }
}

它通过扫描先前识别的集合以查找当前数据行与哪些集合相交来构建输入数据集，然后将这些集合合并为包含所有成员的单个集合(您的规范似乎强加了传递性成员资格……即如果一个字母加入集合 A 和 B，而另一个字母加入集合 B 和 C，您希望 A、B 和 C 都加入一个集合)。

这不是最佳解决方案，但它是可读的。您可以通过维护 Dictionary<char, int> 来避免 O(N^2) 搜索将每个字符映射到包含它的集合。然后不是扫描所有集合，而是对当前行中的每个字符进行简单查找，以构建集合索引列表。但是有更多的“管家”代码采用这种方法；除非您发现一个经过验证的性能问题以更基本的方式进行，否则我不会费心以这种方式实现。

顺便说一句:我有一个模糊的记忆我以前在 Stack Overflow 上看到过这种类型的问题，即这种集合的传递联合。我寻找问题但找不到。您可能会更幸运，并且可能会发现有关该问题及其答案的其他有用信息。