Краткое решение для количества наборов, содержащихся в - PullRequest
Новая
       6

Краткое решение для количества наборов, содержащихся в

1 голос
/ 14 января 2011

Допустим, у меня есть короткий список строк, которые могут содержать дубликаты: <"A", "A", "B", "B", "C", "C", "D", "E", "F">

Тогда, скажем, у меня есть несколько других списков строк, которые могут быть или не быть подмножествами исходного списка.Мне нужно знать:

  1. Охватывает ли второй набор первый набор (например, каждый элемент первого набора также содержится во втором)?
  2. Если 1true, сколько экземпляров второго набора требуется, чтобы воссоздать первый набор?

Итак, в этом случае, если мой второй набор был списком: <"A", "B",«C», «D», «E», «F»>, я бы получил ИСТИНА и 2.

Если бы это был список: <«A», «B», «C»>,Я бы получил ЛОЖЬ.

Если бы мой первый был <"A", "A", "A", "A", "B", "B", "B", "C", "C">:

  • Секунда <<A", "B", "C">: возвращает ИСТИНА и 4.
  • Секунда <<A "," A ",«B», «C»>: возвращает TRUE и 3.

Я знаю, что это можно легко сделать за N x M раз, используя вложенный цикл.Но я ищу (предпочтительно на основе Linq) решение, которое будет кратким и / или оптимизированным.Я играл с Linq.Except , но проблема в том, что он возвращает только отдельные элементы и, следовательно, бесполезен при сравнении списков строк, содержащих дубликаты.

У всех есть уникальные идеи

1 Ответ

5 голосов
/ 14 января 2011

Второй набор «покрывает» первый набор (например, каждый элемент первого набора также содержится во втором)? 

// Assuming that the elements are comparable (strings are);
// if not, need to implement your own IComparer<T>
var doesCover = !original.Except(secondList).Any();

Сколько экземпляров второго набора требуется для воссоздания первого набора? 

var instancesRequired = secondList.GroupBy(e => e)
    .Max(gr => (original.Count(e => e.Equals(gr.Key))
               + gr.Count() - 1) / gr.Count());

Предупреждение: Если оба значения original и secondList не заполнены, то значение doesCover будет истинным, но вычисление instancesRequired приведет к исключению. Поэтому, возможно, стоит специально проверить наличие пустых списков.

...