我的想法是创建一个字典,将原始列表中的每个元素映射到它出现的频率。然后我迭代地递减与子列表中的一项对应的每个项目,直到其中一个值达到零,此时我返回完整迭代的次数。
public static int CountSubsets<T>(this IList<T> list, IList<T> subList)
{
var grouped = list.GroupBy(t => t).ToDictionary(t => t.Key, t => t.Count());
int count = 0;
while (RemoveSubset(grouped, subList))
count++;
return count;
}
private static bool RemoveSubset<T>(Dictionary<T, int> dict, IList<T> subList)
{
foreach (T item in subList)
{
if (dict.ContainsKey(item) && dict[item] > 0)
dict[item]--;
else
return false;
}
return true;
}
不一定是最有效或最优雅的解决方案,但它应该有效。
编辑:这是一种花哨但可能较慢的方法。我对这个很满意:
public static int CountSubsets2<T>(this IList<T> list, IList<T> subList)
{
var main = list.GroupBy(t => t).ToDictionary(t => t.Key, t => t.Count());
var sub = subList.GroupBy(t => t).ToDictionary(t => t.Key, t => t.Count());
return sub.Select(t => main.ContainsKey(t.Key) ? main[t.Key] / t.Value : 0).Min();
}