大多數列表共有的項目

Question

給出一個列表列表（假設有5個列表，要有一個可以工作的實際編號），我可以相對容易地找到所有5個列表共有的項目（請參閱Intersection of multiple lists with IEnumerable.Intersect()），使用下面的代碼的變化：

var list1 = new List<int>() { 1, 2, 3 }; 
var list2 = new List<int>() { 2, 3, 4 }; 
var list3 = new List<int>() { 3, 4, 5 }; 
var listOfLists = new List<List<int>>() { list1, list2, list3 }; 
var intersection = listOfLists.Aggregate((previousList, nextList) => previousList.Intersect(nextList).ToList()); 

現在，讓我們說，intersection結束了包含0項。很有可能有一些4/5列表共有的對象。我將如何去尋找最有效的方式？

我知道我可以通過4列表的所有組合並保存所有結果，但該方法不能很好地擴展（這最終必須在約40個列表中完成）。

如果沒有項目與4個列表共同，那麼搜索將重複查找3/5列表的共同項目等。從視覺上來看，這可以由網格點列表表示，並且我們正在搜索點最重疊的部分。

任何想法？

編輯： 也許最好是看看每個點，並跟蹤它出現在每個列表中的次數，然後創建一個發生率最高的點列表？

Answer 1

您可以從所有列表中選擇所有數字（點），並按值對它們進行分組。然後排序組大小的結果（即名單數量，其中點存在的話），然後選擇最常用的項目：

var mostCommon = listOfLists.SelectMany(l => l) 
          .GroupBy(i => i) 
          .OrderByDescending(g => g.Count()) 
          .Select(g => g.Key) 
          .First(); 
// outputs 3 

而不是隻取第一項，您可以通過更換Take(N)採取First()幾個頂級項目。

---

返回項目進行列表號（名單次數進行排序）：

var mostCommonItems = from l in listOfLists 
         from i in l 
         group i by i into g 
         orderby g.Count() descending 
         select new { 
         Item = g.Key, 
         NumberOfLists = g.Count() 
         }; 

用法（項目是一個強類型的匿名對象）：

var topItem = mostCommonItems.First(); 
var item = topItem.Item; 
var listsCount = topItem.NumberOfLists; 

foreach(var item in mostCommonItems.Take(3)) 
    // iterate over top three items 

Answer 2

可以先合併所有列表，然後使用字典策略如下找到列表的模式。這使得它很快：

/// <summary> 
/// Gets the element that occurs most frequently in the collection. 
/// </summary> 
/// <param name="list"></param> 
/// <returns>Returns the element that occurs most frequently in the collection. 
/// If all elements occur an equal number of times, a random element in 
/// the collection will be returned.</returns> 
public static T Mode<T>(this IEnumerable<T> list) 
{ 
    // Initialize the return value 
    T mode = default(T); 

    // Test for a null reference and an empty list 
    if (list != null && list.Count() > 0) 
    { 
     // Store the number of occurences for each element 
     Dictionary<T, int> counts = new Dictionary<T, int>(); 

     // Add one to the count for the occurence of a character 
     foreach (T element in list) 
     { 
      if (counts.ContainsKey(element)) 
       counts[element]++; 
      else 
       counts.Add(element, 1); 
     } 

     // Loop through the counts of each element and find the 
     // element that occurred most often 
     int max = 0; 

     foreach (KeyValuePair<T, int> count in counts) 
     { 
      if (count.Value > max) 
      { 
       // Update the mode 
       mode = count.Key; 
       max = count.Value; 
      } 
     } 
    } 

    return mode; 
}