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

Question

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

редактировать: извините за то, что не предоставил пример, вот что я имел в виду:

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

{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

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

Вы ищете что-то подобное? Должно быть в значительной степени O (n + m), где n - количество элементов в first и м это количество предметов в 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 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

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

Увидеть ниже:

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();