从多个列表创建组合列表

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包含一些的var List<int>; 我需要的是在combinedCoords其中填充一些新列表,其中包含一些共同数字的组合列表.从这里应该有2个组合列表,第一个将是{0,1,2,3,4,5},第二个将是{7,8,9,10}.为了进一步说明我想说的是,下面是一个图形表示,每个圆圈都是一个列表; 括号中的红色数字表示每个列表的索引.

应该如何看待http://www.aboutireland.ie/lists.png

Answer 1

看来您正在寻找的是连接的组件列表。我在这里回答了一个类似的问题，但这个问题足够不同，我认为它有自己的答案：

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为 a 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]);
        }
    }
}