108

I'm using Ruby 1.8.6 with Rails 1.2.3, and need to determine whether two arrays have the same elements, regardless of whether or not they're in the same order. One of the arrays is guaranteed not to contain duplicates (the other might, in which case the answer is no).

My first thought was

require 'set'
a.to_set == b.to_set

but I was wondering if there was a more efficient or idiomatic way of doing it.

Jeff Ward
  • 16,563
  • 6
  • 48
  • 57
Taymon
  • 24,950
  • 9
  • 62
  • 84
  • possible duplicate of [Ruby - Does array A contain all elements of array B](http://stackoverflow.com/questions/5890717/ruby-does-array-a-contain-all-elements-of-array-b) – fl00r Jun 06 '12 at 19:33
  • Try array.should =~ another_array check http://stackoverflow.com/questions/2978922/rspec-array-should-another-array-but-without-concern-for-order – Athena May 17 '13 at 00:06
  • You could have saved a lot of confusion by: 1) stating whether the elements of the arrays are necessarily sortable; and 2) provide a simple example to clarify what you mean by, "whether two arrays have the same elements" (e.g., do `[1,2]` and `[2,1,1]` have the same elements?) – Cary Swoveland Feb 14 '15 at 19:03
  • Ruby 2.6 has introduced `difference` which offers a solution both very fast and very readable. [More info here.](https://stackoverflow.com/questions/10919783/check-if-two-arrays-have-the-same-contents-in-any-order/56739603#answer-56739603) – SRack Jun 24 '19 at 15:19

9 Answers9

165

This doesn't require conversion to set:

a.sort == b.sort
Mori
  • 27,279
  • 10
  • 68
  • 73
  • No conversion? What is `.uniq.sort` then? Besides `uniq` is similar to `to_set` internally plus additional `.to_a.sort` – Victor Moroz Jun 06 '12 at 18:41
  • Accepting this since it's closest to what I ended up using, though without the `uniq`s. Actually I ended up creating one of the arrays with `Range#to_a`, so I only had to `sort` the other one. – Taymon Jun 07 '12 at 18:59
  • 16
    This won't work if the array contains elements that cannot be simply sorted (e.g. an array of hashes). sahil dhankhar's solution appears to be a more general solution. – brad Aug 24 '13 at 03:15
  • Painfully simple, for small Arrays where performance of sorting them isn't too costly. Thanks. – Joshua Pinter Sep 30 '22 at 19:04
43

for two arrays A and B: A and B have same contents if: (A-B).blank? and (B-A).blank?

or you can just check for: ((A-B) + (B-A)).blank?

Also as suggested by @cort3z this solution als0 works for polymorphic arrays i.e

 A = [1 , "string", [1,2,3]]
 B = [[1,2,3] , "string", 1]
 (A-B).blank? and (B-A).blank? => true
 # while A.uniq.sort == B.uniq.sort will throw error `ArgumentError: comparison of Fixnum with String failed`

::::::::::: EDIT :::::::::::::

As suggested in the comments, above solution fails for duplicates.Although as per the question that is not even required since the asker is not interested in duplicates(he is converting his arrays to set before checking and that masks duplicates and even if you look at the accepeted answer he is using a .uniq operator before checking and that too masks duplicates.). But still if duplicates interests you ,Just adding a check of count will fix the same(as per the question only one array can contain duplicates). So the final solution will be: A.size == B.size and ((A-B) + (B-A)).blank?

Sahil Dhankhar
  • 3,596
  • 2
  • 31
  • 44
  • This will fail if either array contains duplicates. E.g., if `A=[1]` and `B=[1,1]`, both `(A-B)` and `(B-A)` will return blank. See [Array Documentation](http://www.ruby-doc.org/core-2.0.0/Array.html#method-i-2D). – jtpereyda Sep 02 '13 at 18:10
  • @dafrazzman totally agree with you. I have modified my answer to incorporate your feedback.But if you have a close look at the question(or the accepted answer), asker is using: `a.to_set == b.to_set` and the accepted answer is using `a.uniq.sort == b.uniq.sort` and both give exact same result as `((A-B) + (B-A)).blank?` for A=[1] and B=[1,1] agree ? Since he was just asking for an improvement over his original solution , my original solution still works :) . agree? – Sahil Dhankhar Sep 03 '13 at 04:40
  • 1
    This solution is quite nice since it handles objects of multiple types. Say you have `A = [123, "test", [], some_object, nil]` and `B = A#because I am lazy`, then `A.uniq.sort` will throw error (comparison of string and Array failed). – Automatico Feb 19 '15 at 10:20
  • Would this be O(n) then since it's dependent on the array size? (linear) – user3007294 Dec 27 '16 at 20:45
  • 1
    It wouldn't work if the arrays have same size but the repeated elements are not the same. For instance `A = [1, 1, 2]` and `B = [1, 2, 2]` – Boudi Nov 13 '19 at 13:21
  • #blank? is Rails specific. Not everybody is in Rails-land... Use std library method #empty? – Huliax Sep 15 '22 at 21:27
37

Ruby 2.6+

Ruby's introduced difference in 2.6.

This gives a very fast, very readable solution here, as follows:

a = [1, 2, 3, 4, 5, 6]
b = [1, 2, 3, 4, 5, 6]

a.difference(b).any?
# => false
a.difference(b.reverse).any?
# => false

a = [1, 2, 3, 4, 5, 6]
b = [1, 2, 3]
a.difference(b).any?
# => true

However, the reverse isn't true:

a = [1, 2, 3]
b = [1, 2, 3, 4, 5, 6]
a.difference(b).any?
# => false

This means to get the difference in both directions it is necessary to run:

a.difference(b).any? || b.difference(a).any?

Running the benchmarks:

a = Array.new(1000) { rand(100) }
b = Array.new(1000) { rand(100) }

Benchmark.ips do |x|
  x.report('sort')   { a.sort == b.sort }  
  x.report('sort!')  { a.sort! == b.sort! }  
  x.report('to_set') { a.to_set == b.to_set }  
  x.report('minus')  { ((a - b) + (b - a)).empty? }  
  x.report('difference') { a.difference(b).any? }
  x.report('difference two way') { a.difference(b).any? || b.difference(a).any? }
end

                sort     10.175k (± 6.2%) i/s -     50.778k in   5.015112s
               sort!     10.513k (± 6.8%) i/s -     53.212k in   5.089106s
              to_set      4.953k (± 8.8%) i/s -     24.570k in   5.037770s
               minus     15.290k (± 6.6%) i/s -     77.520k in   5.096902s
          difference     25.481k (± 7.9%) i/s -    126.600k in   5.004916s
  difference two way     12.652k (± 8.3%) i/s -     63.232k in   5.038155s

My takeaway would be that difference is a great choice for a one directional diff.

If you need to check in both directions, it's a balance between performance and readability. For me, the readability pips it, but that's a call to be made on a case by case basis.

Hope that helps someone!

SRack
  • 11,495
  • 5
  • 47
  • 60
26

Speed comparsions

require 'benchmark/ips'
require 'set'

a = [1, 2, 3, 4, 5, 6]
b = [1, 2, 3, 4, 5, 6]

Benchmark.ips do |x|
  x.report('sort')   { a.sort == b.sort }  
  x.report('sort!')  { a.sort! == b.sort! }  
  x.report('to_set') { a.to_set == b.to_set }  
  x.report('minus')  { ((a - b) + (b - a)).empty? }  
end  

Warming up --------------------------------------
            sort    88.338k i/100ms
           sort!   118.207k i/100ms
          to_set    19.339k i/100ms
           minus    67.971k i/100ms
Calculating -------------------------------------
            sort      1.062M (± 0.9%) i/s -      5.389M in   5.075109s
           sort!      1.542M (± 1.2%) i/s -      7.802M in   5.061364s
          to_set    200.302k (± 2.1%) i/s -      1.006M in   5.022793s
           minus    783.106k (± 1.5%) i/s -      3.942M in   5.035311s
Morozov
  • 2,719
  • 2
  • 21
  • 23
  • btw order of elemetns does not affect `sort`'s speed – Morozov Apr 21 '16 at 12:10
  • Surprised me... I expected _by-set_ comparison to outperform all others due to sets lookup O(n) time complexity. So that any well implemented sort would require O(n logn). Whereas casting to sets and looking up values would overall make it in O(n) time. – Oleg Afanasyev May 03 '18 at 10:05
  • 3
    I'd expect `to_set` to start outperforming with large enough arrays where O(n logn) would start mattering more than the effort required to convert array to set – Andrius Chamentauskas Feb 12 '19 at 13:55
  • 1
    This is helpful, but not really an answer in itself? Perhaps better adding this to an existing solution? – SRack Jun 24 '19 at 15:33
18

When the elements of a and b are Comparable,

a.sort == b.sort

Correction of @mori's answer based on @steenslag's comment

Jared Beck
  • 16,796
  • 9
  • 72
  • 97
8

If you expect [:a, :b] != [:a, :a, :b] to_set doesn't work. You can use frequency instead:

class Array
  def frequency
    p = Hash.new(0)
    each{ |v| p[v] += 1 }
    p
  end
end

[:a, :b].frequency == [:a, :a, :b].frequency #=> false
[:a, :b].frequency == [:b, :a].frequency #=> true
Victor Moroz
  • 9,167
  • 1
  • 19
  • 23
7

If you know the arrays are of equal length and neither array contains duplicates then this works too:

( array1 & array2 ) == array1

Explanation: the & operator in this case returns a copy of a1 sans any items not found in a2, which is the same as the original a1 iff both arrays have the same contents with no duplicates.

Analyis: Given that the order is unchanged, I'm guessing this is implemented as a double iteration so consistently O(n*n), notably worse for large arrays than a1.sort == a2.sort which should perform with worst-case O(n*logn).

Nat
  • 2,689
  • 2
  • 29
  • 35
  • 2
    Doesn't work always: `a1 = [1,2,3], a2 = [2, 1, 3]` `a1 && a2` returns `[2,1,3]` for me which is not equal to `a1` – Kalyan Raghu Mar 02 '16 at 14:33
  • @Kaylan, don't you mean it only works when `a1==a2`? It may work if `array1` on the right side of the equality is replaced by `array2`, but I doubt that the order of the elements returned by `&` is guaranteed. – Cary Swoveland Mar 25 '16 at 18:15
  • 2
    @KalyanRaghu `&` is a set intersection operator for arrays, `&&` is logical AND - they are very different! – Kimball Sep 05 '18 at 00:30
5

combining & and size may be fast too.

require 'benchmark/ips'
require 'set'

Benchmark.ips do |x|
  x.report('sort')   { a.sort == b.sort }  
  x.report('sort!')  { a.sort! == b.sort! }  
  x.report('to_set') { a.to_set == b.to_set }  
  x.report('minus')  { ((a - b) + (b - a)).empty? }
  x.report('&.size') { a.size == b.size && (a & b).size == a.size }  
end  

Calculating -------------------------------------
                sort    896.094k (±11.4%) i/s -      4.458M in   5.056163s
               sort!      1.237M (± 4.5%) i/s -      6.261M in   5.071796s
              to_set    224.564k (± 6.3%) i/s -      1.132M in   5.064753s
               minus      2.230M (± 7.0%) i/s -     11.171M in   5.038655s
              &.size      2.829M (± 5.4%) i/s -     14.125M in   5.010414s
Todoroki
  • 515
  • 4
  • 12
  • `&` description from ruby official doc `Set Intersection — Returns a new array containing unique elements common to the two arrays. The order is preserved from the original array.` – buncis Jun 25 '23 at 17:44
1

One approach is to iterate over the array with no duplicates

# assume array a has no duplicates and you want to compare to b
!a.map { |n| b.include?(n) }.include?(false)

This returns an array of trues. If any false appears, then the outer include? will return true. Thus you have to invert the whole thing to determine if it's a match.

Ron
  • 1,166
  • 5
  • 15