创建多个列表合并列表

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} 
}; 

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

how it should look http://www.aboutireland.ie/lists.png

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

Answer 2

像这样的事情应该结束了仅包含“关联性”价值观的基础上，我所相信的坐标为您的要求，任何两个清单共同的价值观应该被合并成一个列表：

 bool combinedAny; 
     do 
     { 
      combinedAny = false; 
      for (int i = 0; i < coords.Count; i++) 
      { 
       for (int j = 0; j < i; j++) 
       { 
        if (coords[i].Intersect(coords[j]).Any()) 
        { 
         coords[j] = coords[i].Union(coords[j]).ToList(); 
         coords.RemoveAt(i); 
         combinedAny = true; 
         break; 
        } 
       } 

       if (combinedAny) 
       { 
        break; 
       } 
      } 
     } 
     while (combinedAny);