¿Complemento de dos listas?

Question

Digamos que tengo una lista de cadenas:

A, B, C, D

Luego otra lista de cadenas

B, C, D

Quiero saber qué elementos están en la primera lista que no están en la segunda lista, por lo que el resultado sería A

No sé el nombre del método de extensión para hacer esto. Sé que puedo usar concat, union, intersect para comparaciones de listas similares, pero simplemente no sé el nombre para lograr esta tarea en particular.

Adición, estoy interesado en los duplicados, así que si la primera lista es:

A, A, A, B, C, D

y la segunda lista es

B, C , D

quiero conseguir

a, a, a

Gracias!

Answer 1

Puede utilizar el Except Extension Method para obtener todos los elementos de una lista que no están en una segunda lista:

var result = list1.Except(list2); 

Answer 2

var result = list1.Where(i => !list2.Contains(i)); 

Answer 3

La "excepción" método en el BCL elimina todos los duplicados, lo que no lo es usted quiere.

Si las listas en el problema son grandes, para hacer esto de manera eficiente probablemente desee perder memoria a cambio de ahorrar tiempo. Algo así como:

// yield all members of "sequence" omitting those in "except" 
static IEnumerable<string> Filter(
    this IEnumerable<string> sequence, 
    IEnumerable<string> except) 
{ 
    var set = new HashSet<string>(except); // Burn memory to save time 
    return from item in sequence 
      where !set.Contains(item) 
      select item; 
} 

De esta forma obtendrá una búsqueda rápida cada vez que pruebe un artículo.

de llamadas con

var sequence = new List<string>() { A, B, A, C, D }; 
var except = new List<string>() { B, C }; 
var result = sequence.Filter(except).ToList(); 

Answer 4

Si su definición de duplicados incluye ambas listas y que desea calcular el complemento de manera eficiente, entonces usted tendrá que utilizar una estructura de datos diferente: una bolsa. Una bolsa es un conjunto que permite duplicados.

Aquí hay un método de extensión llamado BagDifference que cuenta eficientemente los duplicados en cualquier lista junto con un programa de muestra inspirado por la respuesta de Eric.

public class Bag<T> : Dictionary<T, int> 
{ 
    public Bag(IEnumerable<T> sequence) 
    { 
     foreach (var item in sequence) 
     { 
      if (!ContainsKey(item)) this[item] = 0; 
      ++this[item]; 
     } 
    } 
} 

public static class EnumerableExtensions 
{ 
    public static IEnumerable<T> BagDifference<T>(this IEnumerable<T> sequence1, IEnumerable<T> sequence2) 
    { 
     var bag1 = new Bag<T>(sequence1); 
     var bag2 = new Bag<T>(sequence2); 
     foreach (var item in bag1.Keys) 
     { 
      var count1 = bag1[item]; 
      var count2 = bag2.ContainsKey(item) ? bag2[item] : 0; 
      var difference = Math.Max(0, count1 - count2); 
      for (int i = 0; i < difference; i++) 
       yield return item; 
     } 
    } 
} 

class Program 
{ 

    static void Main(string[] args) 
    { 
     var sequence = new List<string>() { "A", "B", "A", "C", "D" }; 
     var except = new List<string>() { "A", "B", "C", "C" }; 
     var difference = sequence.BagDifference(except).ToList(); 
    } 
}