c# - 从多个列表创建组合列表

Question

我不太明白这个问题，但我会解释如下，

var combinedCoords = new List<List<int>>();

var coords = new List<List<int>>
{
    new List<int>() {0, 1},
    new List<int>() {0, 1, 2},
    new List<int>() {1, 3, 4, 5},
    new List<int>() {3, 4},
    new List<int>() {7, 8},
    new List<int>() {7, 8, 9},
    new List<int>() {8, 9, 10}
};

这里我有变量 coords其中包含一些 List<int> ;我需要的是在 combinedCoords 中填充一些新列表它将包含一些组合列表，其中有共同的数字。由此应该产生 2 个组合列表，第一个将是 {0,1,2,3,4,5}第二个是{7,8,9,10} .为了进一步说明我想说的话，下面是一个图形表示，每个圆圈都是一个列表；括号中的红色数字表示每个列表的索引。

_{(来源:aboutireland.ie)}

Answer 1

看起来您要找的是 connected component列表。我回答了一个关于这个的类似问题 here , 但这个问题足够不同，我认为它有理由有自己的答案:

var combinedCoords = new List<List<int>>();
foreach(var c in coords)
{
    var merge = new List<List<int>>();
    foreach(var g in combinedCoords)
    {
        if (c.Any(g.Contains))
        {
            merge.Add(g);
        }
    }

    if (merge.Count == 0)
    {
        combinedCoords.Add(c);
    }

    merge.Add(c);
    for(int i = 1; i < merge.Count; i ++)
    {
        foreach(var v in merge[i].Except(merge[0]))
        {
            merge[0].Add(v);
        }

        combinedCoords.Remove(merge[i]);
    }
}

这会产生两个列表:

{ 0, 1, 2, 3, 4, 5 }
{ 7, 8, 9, 10 }

如果重构 coords和 combinedCoords成为List<HashSet<int>> ，算法稍微简单一些，应该表现更好:

var combinedCoords = new List<HashSet<int>>();
foreach(var c in coords)
{
    var merge = new List<HashSet<int>>(combinedCoords.Where(c.Overlaps));
    if (merge.Count == 0)
    {
        combinedCoords.Add(c);
    }
    else
    {
        merge[0].UnionWith(c);
        for(int i = 1; i < merge.Count; i ++)
        {
            merge[0].UnionWith(merge[i]);
            combinedCoords.Remove(merge[i]);
        }
    }
}