大多数列表共有的项目

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