合并具有公共元素的数组

Question

我想合并具有公共元素的数组。我有数组列表如下：

List<int[]> arrList = new List<int[]> 
{ 
    new int[] { 1, 2 }, 
    new int[] { 3, 4, 5 }, 
    new int[] { 2, 7 }, 
    new int[] { 8, 9 }, 
    new int[] { 10, 11, 12 }, 
    new int[] { 3, 9, 13 } 
}; 

，我想合并这些阵列是这样的：

List<int[]> arrList2 = new List<int[]> 
{ 
    new int[] { 1, 2, 7 }, 
    new int[] { 10, 11, 12 }, 
    new int[] { 3, 4, 5, 8, 9, 13 } //order of elements doesn't matter 
}; 

怎么办呢？

Answer 1

让每个数字成为标记图中的一个顶点。对于每个数组，连接给定数组中数字指向的顶点。例如。给定数组（1,5,3）创建两个边（1,5）和（5,3）。然后找到图中所有连接的组件（请参阅：http://en.wikipedia.org/wiki/Connected_component_(graph_theory)）

Answer 2

使用Disjoint-Set Forest data structure。数据结构支持三种操作：

• MakeSet(item） - 创建一个新的集合与单个项目
• Find(item) - 给定一个项目，抬头一组。
• Union(item1, item2) - 给定两个项目，将它们所属的集合连接在一起。

您可以遍历每个数组，并在其第一个元素和每个找到的元素之后调用Union。一旦完成了列表中的所有数组，您将能够通过再次遍历所有数字来检索单个集合，并对它们调用Find(item)。编号为Find的产品应该放在同一个数组中。

这种方法完成合并O(α(n))摊销（α增长非常缓慢，因此对于所有实际目的，它可以被认为是一个小常数）。

Answer 3

我很肯定它不是最好的和最快的解决方案，但工程。

static List<List<int>> Merge(List<List<int>> source) 
{ 
    var merged = 0; 
    do 
    { 
     merged = 0; 
     var results = new List<List<int>>(); 
     foreach (var l in source) 
     { 
      var i = results.FirstOrDefault(x => x.Intersect(l).Any()); 
      if (i != null) 
      { 
       i.AddRange(l); 
       merged++; 
      } 
      else 
      { 
       results.Add(l.ToList()); 
      } 
     } 

     source = results.Select(x => x.Distinct().ToList()).ToList(); 
    } 
    while (merged > 0); 

    return source; 
} 

我用List<List<int>>代替List<int[]>以获取可用AddRange方法。

用法：

var results = Merge(arrList.Select(x => x.ToList()).ToList()); 

// to get List<int[]> instead of List<List<int>> 
var array = results.Select(x => x.ToArray()).ToList();