如何使用 UNION 对 char/string 的数组进行分组？

Question

我有一个二维字符数组，名为 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

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

我该怎么做才能以最佳方式对它进行分组？或者还有其他解决方案吗？

Answer 1

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

这是适用于您给出的示例的非 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) 搜索。然后不是扫描所有集合，而是对当前行中的每个字符进行简单查找，以构建集合索引列表。但是还有更多 "housekeeping" 代码采用这种方法；我不会费心去实现它，除非你发现一个经过验证的性能问题，用更基本的方式来实现它。

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

如何使用 UNION 对 char/string 的数组进行分组？

How to group array of char/string with UNION?

c#

linq

arrays

union

grouping