Как сделать пересечение целочисленных списков при сохранении дубликатов?

Question

Я работаю над наивысшим общим множителем и наименьшим общим множественным назначением, и мне нужно перечислить общие факторы. Пересечение () не будет работать, потому что это удаляет дубликаты. Contains () не будет работать, потому что, если он видит int во втором списке, он возвращает все соответствующие целые числа из первого списка. Есть ли способ сделать пересечение, которое не является отличительным?

edit: извините, что не привел пример, вот что я имел в виду:

если у меня есть наборы:

{1, 2, 2, 2, 3, 3, 4, 5}
{1, 1, 2, 2, 3, 3, 3, 4, 4}

Я бы хотел вывод

{1, 2, 2, 3, 3, 4}

Answer 1

ILookup<int, int> lookup1 = list1.ToLookup(i => i);
ILookup<int, int> lookup2 = list2.ToLookup(i => i);

int[] result =
(
  from group1 in lookup1
  let group2 = lookup2[group1.Key]
  where group2.Any()
  let smallerGroup = group1.Count() < group2.Count() ? group1 : group2
  from i in smallerGroup
  select i
).ToArray();

Выражение where технически необязательно, я чувствую, что оно проясняет намерение.

---

Если вы хотите более краткий код:

ILookup<int, int> lookup2 = list2.ToLookup(i => i);

int[] result =
(
  from group1 in list1.GroupBy(i => i)
  let group2 = lookup2[group1.Key]
  from i in (group1.Count() < group2.Count() ? group1 : group2)
  select i
).ToArray();

Answer 2

Я написал это расширение для решения проблемы:

public static IEnumerable<T> Supersect<T>(this IEnumerable<T> a, List<T> b)
              => a.Where(t => b.Remove(t));

пример:

var a = new List<int> { 1, 2, 2, 2, 3, 3, 4, 5 };
var b = new List<int> { 1, 1, 2, 2, 3, 3, 3, 4, 4};

var result = a.Supersect(b);

результат:

{ 1, 2, 2, 3, 3, 4 }

Answer 3

Вы ищете что-то подобное?Оно должно быть довольно большим O (n + m) , где n - количество элементов в first, а m - количество элементов вsecond.

public static IEnumerable<T> Overlap<T>(this IEnumerable<T> first,
    IEnumerable<T> second, IEqualityComparer<T> comparer = null)
{
    // argument checking, optimisations etc removed for brevity

    var dict = new Dictionary<T, int>(comparer);

    foreach (T item in second)
    {
        int hits;
        dict.TryGetValue(item, out hits);
        dict[item] = hits + 1;
    }

    foreach (T item in first)
    {
        int hits;
        dict.TryGetValue(item, out hits);
        if (hits > 0)
        {
            yield return item;
            dict[item] = hits - 1;
        }
    }
}

Answer 4

Вы можете использовать это обобщенное расширение, которое я написал для другой ответ , это по сути один оператор Linq.Обратите внимание, что он использует Zip, чтобы избежать ненужного полного перечисления совпадающих групп.

public static IEnumerable<T> Commom<T>(
        this IEnumerable<T> source,
        IEnumerable<T> sequence,
        IEqualityComparer<T> comparer = null)
{
    if (sequence == null)
    {
        return Enumerable.Empty<T>();
    }

    if (comparer == null)
    {
        comparer = EqualityComparer<T>.Default;
    }

    return source.GroupBy(t => t, comparer)
        .Join(
            sequence.GroupBy(t => t, comparer),
            g => g.Key,
            g => g.Key,
            (lg, rg) => lg.Zip(rg, (l, r) => l),
            comparer)
        .SelectMany(g => g);
}

это позволяет,

new[] {1, 2, 2, 2, 3, 3, 4, 5}.Common(
    new[] {1, 1, 2, 2, 3, 3, 3, 4, 4}).ToArray()

поддерживать порядок исходной последовательности, как требуется.

Answer 5

Вот один из способов сделать это.Честно говоря, это очень похоже на ответ Дэвида Б., за исключением того, что для объединения используется соединение.

IEnumerable<Foo> seqA = ...
IEnumerable<Foo> seqB = ...

var result = from aGroup in seqA.GroupBy(x => x)
             join bGroup in seqB.GroupBy(x => x) 
                         on aGroup.Key equals bGroup.Key
             let smallerGroup = aGroup.Count() < bGroup.Count() 
                                ? aGroup : bGroup
             from item in smallerGroup
             select item;

Answer 6

• Найдите пересечение двух списков.
• Группировка списков по пересекающимся элементам
• Присоединитесь к группам и выберите минимальное количество для каждого элемента
• Свести в новый список.

См. Ниже:

var intersect = list1.Intersect(list2).ToList();
var groups1 = list1.Where(e => intersect.Contains(e)).GroupBy(e => e);
var groups2 = list2.Where(e => intersect.Contains(e)).GroupBy(e => e);

var allGroups = groups1.Concat(groups2);

return allGroups.GroupBy(e => e.Key)
    .SelectMany(group => group
        .First(g => g.Count() == group.Min(g1 => g1.Count())))
    .ToList();