检查值的一个集合包含另一个

Question

假设我有两个集合如下：

Collection1： “A1” “A1” “M1” “M2”

Collection2： “M2 “ ”M3“ ”M1“ ”A1“ ”A1“ ”A2“

所有的值是字符串值。我想知道Collection1中的所有元素是否都包含在Collection2中，但我无法保证该订单，并且一个集合可能具有多个具有相同值的条目。在这种情况下，Collection2确实包含Collection1，因为Collection2有两个A1，M1和M2。 Theres显而易见的方式：排序两个集合，并弹出值，因为我找到匹配，但我想知道是否有一个更快，更有效的方式来做到这一点。再次与初始收藏我的顺序没有保证或给定值多少次出现

编辑：更改后的设定来收集只是为了清理这些不是套，因为他们可以包含重复值

Answer 1

是的，如果你没有空间限制，有一种更快的方法。 （见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：

如果字符串是非常大的，你很在意空间效率，并与之配合的算法（非常）高的概率为你的作品，然后尝试存储代替每个字符串的散列。这在技术上不是保证工作，但它不工作的概率相当低。

Answer 2

结账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); 
} 

Answer 3

我与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。如果您将它用作比较或控件，但之后不需要内容，则只能这样做。

Answer 4

类似一个

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

Answer 5

我所知道的最简洁的方式：

//determine if Set2 contains all of the elements in Set1 
bool containsAll = Set1.All(s => Set2.Contains(s));