合併具有公共元素的數組

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();