比较两个集合是否相等，而不考虑其中项的顺序
我想比较两个集合(在C#中)，但我不确定有效地实现这一点的最佳方法。
我读过另一个关于Enumerable.SequenceEqual的帖子，但这并不是我想要的。
在我的例子中，如果两个集合都包含相同的项(无论顺序如何)，则它们是相等的。
示例：
collection1 = {1, 2, 3, 4};
collection2 = {2, 4, 1, 3};
collection1 == collection2; // true我通常做的是遍历一个集合中的每个项，看看它是否存在于另一个集合中，然后遍历另一个集合中的每个项，看看它是否存在于第一个集合中。(我从比较长度开始)。
if (collection1.Count != collection2.Count)
return false; // the collections are not equal
foreach (Item item in collection1)
{
if (!collection2.Contains(item))
return false; // the collections are not equal
}
foreach (Item item in collection2)
{
if (!collection1.Contains(item))
return false; // the collections are not equal
}
return true; // the collections are equal然而，这并不完全正确，而且这可能不是比较两个集合是否相等的最有效方法。
我能想到的一个错误的例子是：
collection1 = {1, 2, 3, 3, 4}
collection2 = {1, 2, 2, 3, 4}这将与我的实现相同。我是否应该只计算找到每一项的次数，并确保两个集合中的计数相等？
示例是用某种C#编写的(让我们称之为伪C#)，但是用您想要的任何语言给出答案，这都无关紧要。
注意：为了简单起见，我在示例中使用了整数，但我也希望能够使用引用类型的对象(它们不能正确地作为键，因为只比较对象的引用，而不比较内容)。
回答 20
Stack Overflow用户
发布于 2010-09-25 04:10:30
事实证明，微软的测试框架已经涵盖了这一点：CollectionAssert.AreEquivalent
备注
如果两个集合具有相同数量但顺序相同的相同元素，则这两个集合是等价的。如果元素的值相等，则它们是相等的，如果它们引用相同的对象，则不是。
使用反射器，我修改了AreEquivalent()后面的代码以创建相应的相等比较器。它比现有的答案更完整，因为它考虑了空值，实现了IEqualityComparer，并具有一些效率和边缘情况检查。另外，这是微软:)
public class MultiSetComparer<T> : IEqualityComparer<IEnumerable<T>>
{
private readonly IEqualityComparer<T> m_comparer;
public MultiSetComparer(IEqualityComparer<T> comparer = null)
{
m_comparer = comparer ?? EqualityComparer<T>.Default;
}
public bool Equals(IEnumerable<T> first, IEnumerable<T> second)
{
if (first == null)
return second == null;
if (second == null)
return false;
if (ReferenceEquals(first, second))
return true;
if (first is ICollection<T> firstCollection && second is ICollection<T> secondCollection)
{
if (firstCollection.Count != secondCollection.Count)
return false;
if (firstCollection.Count == 0)
return true;
}
return !HaveMismatchedElement(first, second);
}
private bool HaveMismatchedElement(IEnumerable<T> first, IEnumerable<T> second)
{
int firstNullCount;
int secondNullCount;
var firstElementCounts = GetElementCounts(first, out firstNullCount);
var secondElementCounts = GetElementCounts(second, out secondNullCount);
if (firstNullCount != secondNullCount || firstElementCounts.Count != secondElementCounts.Count)
return true;
foreach (var kvp in firstElementCounts)
{
var firstElementCount = kvp.Value;
int secondElementCount;
secondElementCounts.TryGetValue(kvp.Key, out secondElementCount);
if (firstElementCount != secondElementCount)
return true;
}
return false;
}
private Dictionary<T, int> GetElementCounts(IEnumerable<T> enumerable, out int nullCount)
{
var dictionary = new Dictionary<T, int>(m_comparer);
nullCount = 0;
foreach (T element in enumerable)
{
if (element == null)
{
nullCount++;
}
else
{
int num;
dictionary.TryGetValue(element, out num);
num++;
dictionary[element] = num;
}
}
return dictionary;
}
public int GetHashCode(IEnumerable<T> enumerable)
{
if (enumerable == null) throw new
ArgumentNullException(nameof(enumerable));
int hash = 17;
foreach (T val in enumerable)
hash ^= (val == null ? 42 : m_comparer.GetHashCode(val));
return hash;
}
}示例用法：
var set = new HashSet<IEnumerable<int>>(new[] {new[]{1,2,3}}, new MultiSetComparer<int>());
Console.WriteLine(set.Contains(new [] {3,2,1})); //true
Console.WriteLine(set.Contains(new [] {1, 2, 3, 3})); //false或者，如果您只想直接比较两个集合：
var comp = new MultiSetComparer<string>();
Console.WriteLine(comp.Equals(new[] {"a","b","c"}, new[] {"a","c","b"})); //true
Console.WriteLine(comp.Equals(new[] {"a","b","c"}, new[] {"a","b"})); //false最后，您可以使用您选择的等式比较器：
var strcomp = new MultiSetComparer<string>(StringComparer.OrdinalIgnoreCase);
Console.WriteLine(strcomp.Equals(new[] {"a", "b"}, new []{"B", "A"})); //trueStack Overflow用户
发布于 2008-09-08 17:07:36
一种简单而高效的解决方案是对两个集合进行排序，然后比较它们是否相等：
bool equal = collection1.OrderBy(i => i).SequenceEqual(
collection2.OrderBy(i => i));这个算法是O(N*logN)，而上面的解决方案是O(N^2)。
如果集合具有某些属性，则可以实现更快的解决方案。例如，如果两个集合都是哈希集，则它们不能包含重复项。此外，检查哈希集是否包含某些元素也非常快。在这种情况下，与您的算法类似的算法可能是最快的。
Stack Overflow用户
发布于 2008-09-08 17:00:56
创建一个字典"dict“，然后对第一个集合中的每个成员执行dictmember++；
然后，以同样的方式遍历第二个集合，但对于每个成员都要指定成员--。
最后，循环遍历字典中的所有成员：
private bool SetEqual (List<int> left, List<int> right) {
if (left.Count != right.Count)
return false;
Dictionary<int, int> dict = new Dictionary<int, int>();
foreach (int member in left) {
if (dict.ContainsKey(member) == false)
dict[member] = 1;
else
dict[member]++;
}
foreach (int member in right) {
if (dict.ContainsKey(member) == false)
return false;
else
dict[member]--;
}
foreach (KeyValuePair<int, int> kvp in dict) {
if (kvp.Value != 0)
return false;
}
return true;
}编辑:据我所知，这和最有效的算法是一样的。该算法是O(N)，假设字典使用O(1)个查找。
https://stackoverflow.com/questions/50098
复制相似问题
腾讯云开发者
