Элементы, общие для большинства списков

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 списков и т. Д. Визуально это может быть представлено списками точек сетки, и мы ищем точки которые имеют наибольшее совпадение.

Любые идеи?

EDIT: Возможно, было бы лучше посмотреть на каждую точку и отслеживать, сколько раз она появляется в каждом списке, а затем создать список точек с наивысшим результатом?

Answer 1

Вы можете выбрать все числа (точки) из всех списков и сгруппировать их по значению. Затем сортировать результат по размеру группы (т.е. кол-листы, где точка присутствует) и выберите наиболее распространенный элемент:

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

Вместо того, чтобы только первый пункт, вы можете взять несколько верхних элементов, заменив First() с Take(N).

---

Возвращающихся пункты с числом списков (заказывается по количеству списков):

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