La façon la plus rapide de trouver des éléments communs entre plusieurs listes en C#

Ok, c'trouverez la liste de l'Option des objets qui ont une Valeur figurant dans chaque liste.

var x = from list in optionLists
        from option in list
        where optionLists.All(l => l.Any(o => o.Value == option.Value))
        orderby option.Value
        select option;

Il ne fait pas un "distinct" sélectionner vais retourner plusieurs Option objets, certains d'entre eux avec la même Valeur.

OriginalL'auteur Matt Hamilton

Ici est beaucoup plus efficace de mise en œuvre:

static SortedDictionary<T,bool>.KeyCollection FindCommon<T> (List<List<T>> items)
{
  SortedDictionary<T, bool>
    current_common = new SortedDictionary<T, bool> (),
    common = new SortedDictionary<T, bool> ();

  foreach (List<T> list in items)
  {
    if (current_common.Count == 0)
    {
      foreach (T item in list)
      {
        common [item] = true;
      }
    }
    else
    {
      foreach (T item in list)
      {
        if (current_common.ContainsKey(item))
          common[item] = true;
        else
          common[item] = false;
      }
    }

    if (common.Count == 0)
    {
      current_common.Clear ();
      break;
    }

    SortedDictionary<T, bool>
      swap = current_common;

    current_common = common;
    common = swap;
    common.Clear ();
  }

  return current_common.Keys;
}    

Il fonctionne en créant un ensemble de tous les éléments communs à toutes les listes traitée jusqu'à présent et en comparant chaque liste de cet ensemble, la création d'un ensemble temporaire des éléments communs à la liste actuelle et la liste des éléments courants jusqu'à présent. Effectivement un O(n.m) où n est le nombre de listes et m le nombre d'éléments dans les listes.

Un exemple d'utilisation:

static void Main (string [] args)
{
  Random
    random = new Random();

  List<List<int>>
    items = new List<List<int>>();

  for (int i = 0 ; i < 10 ; ++i)
  {
    List<int>
      list = new List<int> ();

    items.Add (list);

    for (int j = 0 ; j < 100 ; ++j)
    {
      list.Add (random.Next (70));
    }
  }

  SortedDictionary<int, bool>.KeyCollection
    common = FindCommon (items);

  foreach (List<int> list in items)
  {
    list.Sort ();
  }

  for (int i = 0 ; i < 100 ; ++i)
  {
    for (int j = 0 ; j < 10 ; ++j)
    {
      System.Diagnostics.Trace.Write (String.Format ("{0,-4:D} ", items [j] [i]));
    }

    System.Diagnostics.Trace.WriteLine ("");
  }

  foreach (int item in common)
  {
    System.Diagnostics.Trace.WriteLine (String.Format ("{0,-4:D} ", item));
  }
}

OriginalL'auteur Skizz

De tri, puis faire quelque chose qui s'apparente à une opération de fusion-tri.

Fondamentalement, vous voulez faire cela:

1. Récupérer le premier élément de chaque liste
2. Comparer les articles, en cas d'égalité, la sortie
3. Si tous les éléments sont avant les autres, de les trier, récupérer un nouvel élément dans la liste correspondante pour le remplacer, sinon, récupérer de nouveaux éléments à les remplacer tous, de tous la liste
4. Tant que vous avez encore des articles, revenir à 2.

OriginalL'auteur Lasse Vågsæther Karlsen

Vous pouvez le faire en comptant les occurrences de tous les éléments de toutes les listes de ces éléments dont le nombre d'événements est égal au nombre de les listes, sont communs à toutes les listes:

    static List<T> FindCommon<T>(IEnumerable<List<T>> lists)
    {
        Dictionary<T, int> map = new Dictionary<T, int>();
        int listCount = 0; //number of lists

        foreach (IEnumerable<T> list in lists)
        {
            listCount++;
            foreach (T item in list)
            {
                //Item encountered, increment count
                int currCount;
                if (!map.TryGetValue(item, out currCount))
                    currCount = 0;

                currCount++;
                map[item] = currCount;
            }
        }

        List<T> result= new List<T>();
        foreach (KeyValuePair<T,int> kvp in map)
        {
            //Items whose occurrence count is equal to the number of lists are common to all the lists
            if (kvp.Value == listCount)
                result.Add(kvp.Key);
        }

        return result;
    }

OriginalL'auteur logicnp

@Skizz La méthode n'est pas correcte. Elle renvoie également à des éléments qui ne sont pas communes à toutes les listes d'éléments.
Voici la méthode corrigée:

///<summary>.
///The method FindAllCommonItemsInAllTheLists, returns a HashSet that contains all the common items in the lists contained in the listOfLists,
///regardless of the order of the items in the various lists.
///</summary>
///<typeparam name="T"></typeparam>
///<param name="listOfLists"></param>
///<returns></returns>
public static HashSet<T> FindAllCommonItemsInAllTheLists<T>(List<List<T>> listOfLists)
{
if (listOfLists == null || listOfLists.Count == 0)
{
return null;
}
HashSet<T> currentCommon = new HashSet<T>();
HashSet<T> common = new HashSet<T>();
foreach (List<T> currentList in listOfLists)
{
if (currentCommon.Count == 0)
{
foreach (T item in currentList)
{
common.Add(item);
}
}
else
{
foreach (T item in currentList)
{
if (currentCommon.Contains(item))
{
common.Add(item);
}
}
}
if (common.Count == 0)
{
currentCommon.Clear();
break;
}
currentCommon.Clear(); //Empty currentCommon for a new iteration.
foreach (T item in common) /* Copy all the items contained in common to currentCommon. 
*            currentCommon = common; 
* does not work because thus currentCommon and common would point at the same object and 
* the next statement: 
*            common.Clear();
* will also clear currentCommon.
*/
{
if (!currentCommon.Contains(item))
{
currentCommon.Add(item);
}
}
common.Clear();
}
return currentCommon;
}

OriginalL'auteur user2102327