检查值的一个集合包含另一个
假设我有两个集合如下:检查值的一个集合包含另一个
Collection1: “A1” “A1” “M1” “M2”
Collection2: “M2 “ ”M3“ ”M1“ ”A1“ ”A1“ ”A2“
所有的值是字符串值。我想知道Collection1中的所有元素是否都包含在Collection2中,但我无法保证该订单,并且一个集合可能具有多个具有相同值的条目。在这种情况下,Collection2确实包含Collection1,因为Collection2有两个A1,M1和M2。 Theres显而易见的方式:排序两个集合,并弹出值,因为我找到匹配,但我想知道是否有一个更快,更有效的方式来做到这一点。再次与初始收藏我的顺序没有保证或给定值多少次出现
编辑:更改后的设定来收集只是为了清理这些不是套,因为他们可以包含重复值
是的,如果你没有空间限制,有一种更快的方法。 (见space/time tradeoff。)
算法:
在SET2所有元素只需插入到一个哈希表(在C#3.5,这是一个HashSet<string>),然后经过SET1的所有元素,并检查他们是否”重新在哈希表中。该方法更快(Θ(m + n)时间复杂度),但使用O(n)空间。
或者,只是说:
bool isSuperset = new HashSet<string>(set2).IsSupersetOf(set1);
编辑1:
对于那些关注重复的可能性(从而名不副实 “集”)的人,这个想法能容易被扩展:
只需制作一个新的Dictionary<string, int>
代表超级列表中每个单词的计数(添加一个在每次看到现有单词的实例时加入计数,如果该单词不在字典中,则添加计数为1的单词),然后遍历子列表并每次减少计数。如果字典和中存在每个单词,则当您尝试减小该单词时count不会为零,那么该子集实际上是一个子列表;否则,你有一个单词的实例太多(或根本不存在),所以它不是一个真正的子列表。
编辑2:
如果字符串是非常大的,你很在意空间效率,并与之配合的算法(非常)高的概率为你的作品,然后尝试存储代替每个字符串的散列。这在技术上不是保证工作,但它不工作的概率相当低。
只需使用['IsSubsetOf'](http://msdn.microsoft.com/en-us/library/bb358446.aspx):) – porges 2011-03-02 02:43:56
@Porges:编辑:我以为你的意思是'IsSubsetOf'是一个LINQ方法,但它不是 - 这种方法真的是你的意思,还是你的意思是'IsSupersetOf'? (我认为在子集上使用'IsSubsetOf'比在超集上使用'IsSupersetOf'慢。) – Mehrdad 2011-03-02 02:49:48
如果你有重复的话,使用集合和集合论是不可行的。 “一个集合是一个不包含重复元素的集合”,逻辑做出了这个假设。如果您从Set2中删除第二个A1,则来自Set1的两个A1仍将被视为“in”Set2。 – 2011-03-02 02:54:37
结账linq. ..
string[] set1 = {"A1", "A1", "M1", "M2" };
string[] set2 = { "M2", "M3", "M1", "A1", "A1", "A2" };
var matching = set1.Intersect(set2);
foreach (string x in matching)
{
Console.WriteLine(x);
}
我与HashSet的,相交,和其他集理论的答案看到的问题是,你确实包含重复,“一套是不包含重复元素的集合”。这是一种处理重复案例的方法。
var list1 = new List<string> { "A1", "A1", "M1", "M2" };
var list2 = new List<string> { "M2", "M3", "M1", "A1", "A1", "A2" };
// Remove returns true if it was able to remove it, and it won't be there to be matched again if there's a duplicate in list1
bool areAllPresent = list1.All(i => list2.Remove(i));
编辑:我从SET1和SET2更名为LIST1和List2安抚迈赫达德。
编辑2:评论意味着它,但我想明确指出,这确实会改变list2。如果您将它用作比较或控件,但之后不需要内容,则只能这样做。
@druttka:+1用于调用它们'Set1'和'Set2',尽管你反对这种说法......这很有趣。:P 而这是非常缓慢的。 – Mehrdad 2011-03-02 02:56:38
@Mehrdad我用他的例子中的名字。 “疯狂”似乎是一个相对术语,至少它不像其他地方发布的集合论解决方案那样工作。 – 2011-03-02 02:58:31
@druttka:这不是相对的,因为这是O(m * n),而另一个解是O(m + n)。无论是不恰当的还是其他问题都是一个不同的问题,但这种解决方案是一个很慢的恕我直言。 :( – Mehrdad 2011-03-02 03:00:09
类似一个
string[] set1 = new string[] { "a1","a2","a3","a4","a5","aa","ab" };
string[] set2 = new string[] {"m1","m2","a4","a6","a1" };
var a = set1.Select(set => set2.Contains(set));
,因为返回值的含义并不明显,您应该明确输入。什么是'一个'? – jeromeyers 2014-03-04 19:46:56
它返回set1中set1的所有元素的列表(或集合或任何您可能想称之为的)。因此,它不能正确地检查set2是否包含set1的所有元素,因为只要set2包含set1的1个元素,“Any()”将始终为真。 – 2015-05-07 10:04:25
我所知道的最简洁的方式:
//determine if Set2 contains all of the elements in Set1
bool containsAll = Set1.All(s => Set2.Contains(s));
显然是最好的答案。不知道它是如何衡量性能。但在我的情况下,这是完美的。 – jeromeyers 2014-03-04 19:59:26
如果要确定Set1和Set2是否包含相同的元素,而不考虑您可以执行的顺序: if(Set1.All(s => Set2.Contains(s))&& Set2.All(s => Set1.Contains( s))){...} – jeromeyers 2014-03-20 18:29:39
伟大的解决方案!如果您需要知道可以使用的馆藏之间的共同对象: a.Intersect(b)其中a和b是集合。 – 2017-03-16 20:59:08
总猜测出蓝色的,这是家庭作业(或可能的面试问题)? – Mehrdad 2011-03-02 02:38:29
那么,我正在写一些游戏的逻辑,我想添加一个功能,其中一堆行动/攻击可以堆叠在一起,然后减少到另一个 – Megatron 2011-03-02 02:42:15
@ user127817:哈哈好吧,对不起!我们在这里问了很多问题(以防止直接回答家庭作业问题),而且我会认为对于不问*作业的用户来说这非常烦人。有趣的问题! :) – Mehrdad 2011-03-02 02:47:14