6

Given two arrays of equal size, how can I find the number of matching elements disregarding the position?
For example:

  1. [0,0,5] and [0,5,5] would return a match of 2 since there is one 0 and one 5 in common;
  2. [1,0,0,3] and [0,0,1,4] would return a match of 3 since there are two matches of 0 and one match of 1;
  3. [1,2,2,3] and [1,2,3,4] would return a match of 3.

I tried a number of ideas, but they all tend to get rather gnarly and convoluted. I'm guessing there is some nice Ruby idiom, or perhaps a regex that would be an elegant answer to this solution.

potashin
  • 44,205
  • 11
  • 83
  • 107
Joe Balsamo
  • 63
  • 6
  • My first guess would have been `array_one & array_two`.length, but that doesn't include unique elements – Richard Hamilton Jun 14 '15 at 17:01
  • Good question, well stated. – Cary Swoveland Jun 14 '15 at 18:34
  • @CarySwoveland: Totally agree with you, but title is vague – it is unlikely that people with the same issue will reach this post. P.S. I was also having a bad time formulating a non-cumbersome title for this.. – potashin Jun 14 '15 at 18:56
  • @suslov, you have a point. How about, "Determine the number of elements in one array that map 1-1 to the same element in a second array."? – Cary Swoveland Jun 14 '15 at 19:09
  • Joe, after reading your profile I thought you'd be interested in [this picture](http://media.news.harvard.edu/gazette/wp-content/uploads/2012/09/Turing_Mark-I_380.jpg) of me working on my first computer. – Cary Swoveland Jun 14 '15 at 19:49
  • 1
    @CarySwoveland, love that photo! That's just awesome. Sorry to you guys for the poorly worded question, but I had a devil of a time expressing in words what was easier shown in a few example. Appreciate all of your help. – Joe Balsamo Jun 14 '15 at 20:27

5 Answers5

3
(arr1 & arr2).map { |i| [arr1.count(i), arr2.count(i)].min }.inject(0, &:+)

Here (arr1 & arr2) return list of uniq values that both arrays contain, arr.count(i) counts the number of items i in the array.

Andrew Kozin
  • 1,012
  • 9
  • 17
3

You can accomplish it with count:

a.count{|e| index = b.index(e) and b.delete_at index }

Demonstration

or with inject:

a.inject(0){|count, e| count + ((index = b.index(e) and b.delete_at index) ? 1 : 0)}

Demonstration

or with select and length (or it's alias – size):

a.select{|e| (index = b.index(e) and b.delete_at index)}.size

Demonstration

Results:

  1. a, b = [0,0,5], [0,5,5] output: => 2;
  2. a, b = [1,2,2,3], [1,2,3,4] output: => 3;
  3. a, b = [1,0,0,3], [0,0,1,4] output => 3.
potashin
  • 44,205
  • 11
  • 83
  • 107
  • 1
    I think this is the solution! I need to run my rspec's on it, as I got bit by a number of edge cases in my own attempt, but I'm keeping my fingers crossed. Will let you know after my suite runs. In the meantime, thank you very much. – Joe Balsamo Jun 14 '15 at 17:43
  • 1
    It passed my tests! Thank you again, suslov, I've credited you in my source code. My obliged. – Joe Balsamo Jun 14 '15 at 17:56
  • 1
    Nice. You can reduce the work with `a.select{|e| ndx = b.index(e) && b.delete_at ndx }.count`. Note this doesn't work if `nil` elements are present. Also, it mutates `b`, so you may wish to operate on a copy of `b`. – Cary Swoveland Jun 14 '15 at 18:26
  • Wait a minute. I may have spoken too soon :-). – Cary Swoveland Jun 14 '15 at 18:54
  • 1
    Yes. (I think the latter is more in keeping with the way `inject` works.) – Cary Swoveland Jun 14 '15 at 19:00
  • 1
    I just have to say that `select` is a **really** nice piece of ruby code! My original motivation to ask here was to learn the "Ruby way" of doing it, and I was well schooled. Just beautiful! I'm amazed, actually. Thanks again, my code is working beautifully and I am happily adding new features rather than banging my head. – Joe Balsamo Jun 15 '15 at 01:43
2

Another use for the mighty (and much needed) Array#difference, which I defined in my answer here. This method is similar to Array#-. The difference between the two methods is illustrated in the following example:

a = [1,2,3,4,3,2,4,2]
b = [2,3,4,4,4]
a - b          #=> [1]
a.difference b #=>  [1, 3, 2, 2]

For the present application:

def number_matches(a,b)
  left_in_b = b
  a.reduce(0) do |t,e|
    if left_in_b.include?(e)
      left_in_b = left_in_b.difference [e]
      t+1
    else
      t
    end
  end
end

number_matches [0,0,5],   [0,5,5]   #=> 2
number_matches [1,0,0,3], [0,0,1,4] #=> 3
number_matches [1,0,0,3], [0,0,1,4] #=> 3
Community
  • 1
  • 1
Cary Swoveland
  • 106,649
  • 6
  • 63
  • 100
1

Using the multiset gem:

(Multiset.new(a) & Multiset.new(b)).size

Multiset is like Set, but allows duplicate values. & is the "set intersection" operator (return all things that are in both sets).

Wayne Conrad
  • 103,207
  • 26
  • 155
  • 191
  • 1
    From rubygems.org description: Unlike ordinary set(see Ruby documentation for "set" library), multiset can contain two or more same items. Set[:a,:b,:c,:b,:b,:c] # => # Multiset[:a,:b,:c,:b,:b,:c] # => # Multisets are typically used for counting elements and their appearances in collections. Very interesting. Thank you for making me aware of this gem. – Joe Balsamo Jun 15 '15 at 17:46
0

I don't think this is an ideal answer, because it's a bit complex, but...

def count(arr)
  arr.each_with_object(Hash.new(0)) { |e,h| h[e] += 1 }
end

def matches(a1, a2)
  m = 0
  a1_counts = count(a1)
  a2_counts = count(a2)
  a1_counts.each do |e, c|
    m += [a1_counts, a2_counts].min
  end
  m
end

Basically, first write a method that creates a hash from an array of the number of times each element appears. Then, use those to sum up the smallest number of times each element appears in both arrays.

MrTheWalrus
  • 9,670
  • 2
  • 42
  • 66