Comparing two collections for equality irrespective of the order of items in them

Question

I would like to compare two collections  in C    but I m not sure of the best way to implement this efficiently   I ve read the other thread about Enumerable SequenceEqual  but it s not exactly what I m looking for   In my case  two collections would be equal if they both contain the same items  no matter the order    Example   collection1    1  2  3  4   collection2    2  4  1  3    collection1    collection2     true   What I usually do is to loop through each item of one collection and see if it exists in the other collection  then loop through each item of the other collection and see if it exists in the first collection   I start by comparing the lengths    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   However  this is not entirely correct  and it s probably not the most efficient way to do compare two collections for equality   An example I can think of that would be wrong is   collection1    1  2  3  3  4  collection2    1  2  2  3  4    Which would be equal with my implementation  Should I just count the number of times each item is found and make sure the counts are equal in both collections     The examples are in some sort of C   let s call it pseudo-C    but give your answer in whatever language you wish  it does not matter   Note  I used integers in the examples for simplicity  but I want to be able to use reference-type objects too  they do not behave correctly as keys because only the reference of the object is compared  not the content

User · Answer

A duplicate post of sorts  but check out my solution for comparing collections  It s pretty simple   This will perform an equality comparison regardless of order   var list1   new      Bill    Bob    Sally     var list2   new      Bob    Bill    Sally     bool isequal   list1 Compare list2  IsSame    This will check to see if items were added   removed   var list1   new      Billy    Bob     var list2   new      Bob    Sally     var diff   list1 Compare list2   var onlyinlist1   diff Removed    Billy var onlyinlist2   diff Added      Sally var inbothlists   diff Equal      Bob   This will see what items in the dictionary changed   var original   new Dictionary lt int  string gt        1   a       2   b       var changed   new Dictionary lt int  string gt        1   aaa       2   b       var diff   original Compare changed   x  y    gt  x Value    y Value   x  y    gt  x Value    y Value   foreach  var item in diff Different    Console Write   0  changed to  1    item Key Value  item Value Value     Will output  a changed to aaa   Original post here

User · Answer

It turns out Microsoft already has this covered in its testing framework  CollectionAssert AreEquivalent  Remarks Two collections are equivalent if they have the same elements in the same quantity  but in any order  Elements are equal if their values are equal  not if they refer to the same object   Using reflector  I modified the code behind AreEquivalent   to create a corresponding equality comparer  It is more complete than existing answers  since it takes nulls into account  implements IEqualityComparer and has some efficiency and edge case checks  plus  it s Microsoft    public class MultiSetComparer lt T gt    IEqualityComparer lt IEnumerable lt T gt  gt        private readonly IEqualityComparer lt T gt  m comparer      public MultiSetComparer IEqualityComparer lt T gt  comparer   null                m comparer   comparer    EqualityComparer lt T gt  Default             public bool Equals IEnumerable lt T gt  first  IEnumerable lt T gt  second                if  first    null              return second    null           if  second    null              return false           if  ReferenceEquals first  second               return true           if  first is ICollection lt T gt  firstCollection  amp  amp  second is ICollection lt T gt  secondCollection                        if  firstCollection Count    secondCollection Count                  return false               if  firstCollection Count    0                  return true                     return  HaveMismatchedElement first  second              private bool HaveMismatchedElement IEnumerable lt T gt  first  IEnumerable lt T gt  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 lt T  int gt  GetElementCounts IEnumerable lt T gt  enumerable  out int nullCount                var dictionary   new Dictionary lt T  int gt  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 lt T gt  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           Sample usage  var set   new HashSet lt IEnumerable lt int gt  gt  new    new   1 2 3    new MultiSetComparer lt int gt      Console WriteLine set Contains new     3 2 1       true Console WriteLine set Contains new     1  2  3  3       false  Or if you just want to compare two collections directly  var comp   new MultiSetComparer lt string gt     Console WriteLine comp Equals new     quot a quot   quot b quot   quot c quot    new     quot a quot   quot c quot   quot b quot        true Console WriteLine comp Equals new     quot a quot   quot b quot   quot c quot    new     quot a quot   quot b quot        false  Finally  you can use your an equality comparer of your choice  var strcomp   new MultiSetComparer lt string gt  StringComparer OrdinalIgnoreCase   Console WriteLine strcomp Equals new     quot a quot    quot b quot    new     quot B quot    quot A quot        true

User · Answer

This is my  heavily influenced by D Jennings  generic implementation of the comparison method  in C          lt summary gt      Represents a service used to compare two collections for equality       lt  summary gt       lt typeparam name  T  gt The type of the items in the collections  lt  typeparam gt  public class CollectionComparer lt T gt             lt summary gt          Compares the content of two collections for equality           lt  summary gt           lt param name  foo  gt The first collection  lt  param gt           lt param name  bar  gt The second collection  lt  param gt           lt returns gt True if both collections have the same content  false otherwise  lt  returns gt      public bool Execute ICollection lt T gt  foo  ICollection lt T gt  bar                   Declare a dictionary to count the occurence of the items in the collection         Dictionary lt T  int gt  itemCounts   new Dictionary lt T int gt                 Increase the count for each occurence of the item in the first collection         foreach  T item in foo                        if  itemCounts ContainsKey item                                 itemCounts item                               else                               itemCounts item    1                                      Wrap the keys in a searchable list         List lt T gt  keys   new List lt T gt  itemCounts Keys               Decrease the count for each occurence of the item in the second collection         foreach  T item in bar                           Try to find a key for the item                The keys of a dictionary are compared by reference  so we have to                find the original key that is equivalent to the  item                 You may want to override   Equals  to define what it means for                two  T  objects to be equal             T key   keys Find                  delegate T listKey                                        return listKey Equals item                                       Check if a key was found             if key    null                                itemCounts key --                            else                                  There was no occurence of this item in the first collection  thus the collections are not equal                 return false                                      The count of each item should be 0 if the contents of the collections are equal         foreach  int value in itemCounts Values                        if  value    0                                return false                                      The collections are equal         return true

User · Answer

If comparing for the purpose of Unit Testing Assertions  it may make sense to throw some efficiency out the window and simply convert each list to a string representation  csv  before doing the comparison   That way  the default test Assertion message will display the differences within the error message   Usage   using Microsoft VisualStudio TestTools UnitTesting      define collection1  collection2       Assert Equal collection1 OrderBy c  gt c  ToCsv    collection2 OrderBy c  gt c  ToCsv       Helper Extension Method   public static string ToCsv lt T gt       this IEnumerable lt T gt  values      Func lt T  string gt  selector      string joinSeparator              if  selector    null                if  typeof T     typeof Int16                 typeof T     typeof Int32                 typeof T     typeof Int64                         selector    v    gt  Convert ToInt64 v  ToStringInvariant                      else if  typeof T     typeof decimal                         selector    v    gt  Convert ToDecimal v  ToStringInvariant                      else if  typeof T     typeof float                     typeof T     typeof double                         selector    v    gt  Convert ToDouble v  ToString CultureInfo InvariantCulture                     else                       selector    v    gt  v ToString                         return String Join joinSeparator  values Select v   gt  selector v

User · Answer

erickson is almost right  since you want to match on counts of duplicates  you want a Bag   In Java  this looks something like    new HashBag collection1   equals new HashBag collection2     I m sure C  has a built-in Set implementation   I would use that first  if performance is a problem  you could always use a different Set implementation  but use the same Set interface

User · Answer

In many cases the only suitable answer is the one of Igor Ostrovsky   other answers are based on objects hash code   But when you generate an hash code for an object you do so only based on his IMMUTABLE fields - such as object Id field  in case of a database entity  - Why is it important to override GetHashCode when Equals method is overridden   This means   that if you compare two collections   the result might be true of the compare method even though the fields of the different items are non-equal    To deep compare collections   you need to use Igor s method and implement IEqualirity    Please read the comments of me and mr Schnider s on his most voted post   James

User · Answer

If you use Shouldly  you can use ShouldAllBe with Contains    collection1    1  2  3  4   collection2    2  4  1  3    collection1 ShouldAllBe item  gt collection2 Contains item       true   And finally  you can write an extension    public static class ShouldlyIEnumerableExtensions       public static void ShouldEquivalentTo lt T gt  this IEnumerable lt T gt  list  IEnumerable lt T gt  equivalent                list ShouldAllBe l   gt  equivalent Contains l              UPDATE  A optional parameter exists on ShouldBe method   collection1 ShouldBe collection2  ignoreOrder  true      true

User · Answer

Here is a solution which is an improvement over this one   public static bool HasSameElementsAs lt T gt           this IEnumerable lt T gt  first           IEnumerable lt T gt  second           IEqualityComparer lt T gt  comparer   null                var firstMap   first              GroupBy x   gt  x  comparer               ToDictionary x   gt  x Key  x   gt  x Count    comparer            var secondMap   second              GroupBy x   gt  x  comparer               ToDictionary x   gt  x Key  x   gt  x Count    comparer            if  firstMap Keys Count    secondMap Keys Count              return false           if  firstMap Keys Any k1   gt   secondMap ContainsKey k1                return false           return firstMap Keys All x   gt  firstMap x     secondMap x

User · Answer

static bool SetsContainSameElements lt T gt  IEnumerable lt T gt  set1  IEnumerable lt T gt  set2        var setXOR   new HashSet lt T gt  set1       setXOR SymmetricExceptWith set2       return  setXOR Count    0       Solution requires  NET 3 5 and the System Collections Generic namespace  According to Microsoft  SymmetricExceptWith is an O n   m  operation  with n representing the number of elements in the first set and m representing the number of elements in the second  You could always add an equality comparer to this function if necessary

User · Answer

Create a Dictionary  dict  and then for each member in the first collection  do dict member      Then  loop over the second collection in the same way  but for each member do dict member --   At the end  loop over all of the members in the dictionary       private bool SetEqual  List lt int gt  left  List lt int gt  right             if  left Count    right Count              return false           Dictionary lt int  int gt  dict   new Dictionary lt int  int gt              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 lt int  int gt  kvp in dict                if  kvp Value    0                  return false                     return true           Edit  As far as I can tell this is on the same order as the most efficient algorithm  This algorithm is O N   assuming that the Dictionary uses O 1  lookups

User · Answer

EDIT  I realized as soon as I posed that this really only works for sets -- it will not properly deal with collections that have duplicate items   For example   1  1  2   and   2  2  1   will be considered equal from this algorithm s perspective   If your collections are sets  or their equality can be measured that way   however  I hope you find the below useful   The solution I use is   return c1 Count    c2 Count  amp  amp  c1 Intersect c2  Count      c1 Count    Linq does the dictionary thing under the covers  so this is also O N     Note  it s O 1  if the collections aren t the same size    I did a sanity check using the  SetEqual  method suggested by Daniel  the OrderBy SequenceEquals method suggested by Igor  and my suggestion   The results are below  showing O N LogN  for Igor and O N  for mine and Daniel s   I think the simplicity of the Linq intersect code makes it the preferable solution     Test Latency ms    N  SetEquals  OrderBy  Intersect     1024  0  0  0     2048  0  0  0     4096  31 2468  0  0     8192  62 4936  0  0     16384  156 234  15 6234  0     32768  312 468  15 6234  46 8702     65536  640 5594  46 8702  31 2468     131072  1312 3656  93 7404  203 1042     262144  3765 2394  187 4808  187 4808     524288  5718 1644  374 9616  406 2084     1048576  11420 7054  734 2998  718 6764     2097152  35090 1564  1515 4698  1484 223

User · Answer

Allowing for duplicates in the IEnumerable lt T gt   if sets are not desirable possible  and  ignoring order  you should be able to use a  GroupBy      I m not an expert on the complexity measurements  but my rudimentary understanding is that this should be O n   I understand O n 2  as coming from performing an O n  operation inside another O n  operation like ListA Where a   gt  ListB Contains a   ToList    Every item in ListB is evaluated for equality against each item in ListA   Like I said  my understanding on complexity is limited  so correct me on this if I m wrong    public static bool IsSameAs lt T  TKey gt  this IEnumerable lt T gt  source  IEnumerable lt T gt  target  Expression lt Func lt T  TKey gt  gt  keySelectorExpression                   check the object         if  source    null  amp  amp  target    null  return true          if  source    null    target    null  return false           var sourceList   source ToList            var targetList   target ToList                check the list count      1 1 1        1 1 1 1           if  sourceList Count    targetList Count  return false           var keySelector   keySelectorExpression Compile            var groupedSourceList   sourceList GroupBy keySelector  ToList            var groupedTargetList   targetList GroupBy keySelector  ToList                check that the number of grouptings match      1 1 2 3 4        1 1 2 3 4 5           var groupCountIsSame   groupedSourceList Count    groupedTargetList Count          if   groupCountIsSame  return false              check that the count of each group in source has the same count in target    for values   1 1 2 3 4    amp    1 1 1 2 3 4              key count              1 2  2 1  3 1  4 1        1 3  2 1  3 1  4 1           var countsMissmatch   groupedSourceList Any sourceGroup   gt                                                                                                                        var targetGroup   groupedTargetList Single y   gt  y Key Equals sourceGroup Key                                                                return sourceGroup Count      targetGroup Count                                                                        return  countsMissmatch

User · Answer

Here s my extension method variant of ohadsc s answer  in case it s useful to someone  static public class EnumerableExtensions        static public bool IsEquivalentTo lt T gt  this IEnumerable lt T gt  first  IEnumerable lt T gt  second                if   first    null      second    null               return false           if   object ReferenceEquals first  second   amp  amp   first    null                         if  first Count      second Count                    return false               if   first Count      0   amp  amp  HaveMismatchedElement lt T gt  first  second                   return false                     return true             private static bool HaveMismatchedElement lt T gt  IEnumerable lt T gt  first  IEnumerable lt T gt  second                int firstCount          int secondCount           var firstElementCounts   GetElementCounts lt T gt  first  out firstCount           var secondElementCounts   GetElementCounts lt T gt  second  out secondCount            if  firstCount    secondCount              return true           foreach  var kvp in firstElementCounts                        firstCount   kvp Value              secondElementCounts TryGetValue kvp Key  out secondCount                if  firstCount    secondCount                  return true                     return false             private static Dictionary lt T  int gt  GetElementCounts lt T gt  IEnumerable lt T gt  enumerable  out int nullCount                var dictionary   new Dictionary lt T  int gt             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             static private int GetHashCode lt T gt  IEnumerable lt T gt  enumerable                int hash   17           foreach  T val in enumerable OrderBy x   gt  x               hash   hash   23   val GetHashCode             return hash

User · Answer

You could use a Hashset   Look at the SetEquals method

User · Answer

Why not use  Except       Create the IEnumerable data sources  string   names1   System IO File ReadAllLines            names1 txt    string   names2   System IO File ReadAllLines            names2 txt       Create the query  Note that method syntax must be used here  IEnumerable lt string gt  differenceQuery     names1 Except names2      Execute the query  Console WriteLine  The following lines are in names1 txt but not names2 txt    foreach  string s in differenceQuery       Console WriteLine s     http   msdn microsoft com en-us library bb397894 aspx

User · Answer

In the case of no repeats and no order  the following EqualityComparer can be used to allow collections as dictionary keys   public class SetComparer lt T gt    IEqualityComparer lt IEnumerable lt T gt  gt   where T IComparable lt T gt        public bool Equals IEnumerable lt T gt  first  IEnumerable lt T gt  second                if  first    second              return true          if   first    null      second    null               return false          return first ToHashSet   SetEquals second              public int GetHashCode IEnumerable lt T gt  enumerable                int hash   17           foreach  T val in enumerable OrderBy x   gt  x               hash   hash   23   val GetHashCode             return hash            Here is the ToHashSet   implementation I used  The hash code algorithm comes from Effective Java  by way of Jon Skeet

User · Answer

This simple solution forces the IEnumerable s generic type to implement IComparable  Because of  OrderBy s definition   If you don t want to make such an assumption but still want use this solution  you can use the following piece of code     bool equal   collection1 OrderBy i   gt  i  GetHashCode        SequenceEqual collection2 OrderBy i   gt  i  GetHashCode

User · Answer

There are many solutions to this problem   If you don t care about duplicates  you don t have to sort both  First make sure that they have the same number of items  After that sort one of the collections  Then binsearch each item from the second collection in the sorted collection  If you don t find a given item stop and return false  The complexity of this  - sorting the first collection  NLog N  - searching each item from second into the first  NLOG N  so you end up with 2 N LOG N  assuming that they match and you look up everything  This is similar to the complexity of sorting both  Also this gives you the benefit to stop earlier if there s a difference  However  keep in mind that if both are sorted before you step into this comparison and you try sorting by use something like a qsort  the sorting will be more expensive  There are optimizations for this  Another alternative  which is great for small collections where you know the range of the elements is to use a bitmask index  This will give you a O n  performance  Another alternative is to use a hash and look it up  For small collections it is usually a lot better to do the sorting or the bitmask index  Hashtable have the disadvantage of worse locality so keep that in mind  Again  that s only if you don t care about duplicates  If you want to account for duplicates go with sorting both

User · Answer

A simple and fairly efficient solution is to sort both collections and then compare them for equality   bool equal   collection1 OrderBy i   gt  i  SequenceEqual                   collection2 OrderBy i   gt  i      This algorithm is O N logN   while your solution above is O N 2    If the collections have certain properties  you may be able to implement a faster solution  For example  if both of your collections are hash sets  they cannot contain duplicates  Also  checking whether a hash set contains some element is very fast  In that case an algorithm similar to yours would likely be fastest

[.net] Comparing two collections for equality irrespective of the order of items in them

Examples related to .net

Examples related to collections

Examples related to comparison

Examples related to equality