c# - 包含的集合数量的简明解决方案

Question

假设我有一个简短的字符串列表，其中可以包含重复项:<"A"、"A"、"B"、"B"、"C"、"C"、"D"、"E", "F">

然后假设我有一些其他字符串列表，它们可能是也可能不是原始列表的子集。我需要知道:

1. 第二组是否“覆盖”了第一组(例如，第一组中的每一项是否也包含在第二组中)？
2. 如果 1 为真，则需要多少个第二组实例才能重新创建第一组？

因此，在这种情况下，如果我的第二组是列表:<"A"、"B"、"C"、"D"、"E"、"F">，我将得到 TRUE 和 2。

如果是列表:<"A", "B", "C">，我会得到 FALSE。

如果我的第一个是<"A", "A", "A", "A", "B", "B", "B", "C", "C">:

• 第二个是 <"A", "B", "C">:返回 TRUE 和 4。
• 第二个是 <"A", "A", "B", "C">:返回 TRUE 和 3。

我知道这可以使用嵌套循环在 N x M 时间内轻松完成。但我正在寻找一种(最好是基于 Linq 的)简洁和/或优化的解决方案。我玩过 Linq.Except 但问题是它只返回不同的元素，因此在比较包含重复项的字符串列表时毫无用处。

大家有什么独特的想法吗？

Answer 1

Does the second set "cover" the first set (e.g., is every item in the first set also contained in the second)?

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

How many instances of the second set does it take to recreate the first set?

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

警告:如果 original 和 secondList 都为空，则 doesCover 将为真，但计算instancesRequired 将抛出异常。因此可能需要专门检查空列表。