Counting matching elements in an array

Question

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

[0,0,5] and [0,5,5] would return a match of 2 since there is one 0 and one 5 in common;
[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;
[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.

My first guess would have been array_one & array_two.length, but that doesn't include unique elements — Richard Hamilton
– Richard Hamilton, Commented Jun 14, 2015 at 17:01
@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.. — souslov
– souslov, Commented Jun 14, 2015 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
– Cary Swoveland, Commented Jun 14, 2015 at 19:09
@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
– Joe Balsamo, Commented Jun 14, 2015 at 20:27

souslov · Accepted Answer · 2015-06-16 07:56:47Z

4

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:

a, b = [0,0,5], [0,5,5] output: => 2;
a, b = [1,2,2,3], [1,2,3,4] output: => 3;
a, b = [1,0,0,3], [0,0,1,4] output => 3.

edited Jun 16, 2015 at 7:56

answered Jun 14, 2015 at 17:24

souslov

44.7k11 gold badges92 silver badges113 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

Joe Balsamo Over a year ago

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 Over a year ago

It passed my tests! Thank you again, suslov, I've credited you in my source code. My obliged.

Cary Swoveland Over a year ago

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 Over a year ago

Yes. (I think the latter is more in keeping with the way inject works.)

Joe Balsamo Over a year ago

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.

|

Andrew Kozin · Accepted Answer · 2015-06-14 17:51:11Z

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.

edited Jun 14, 2015 at 17:51

answered Jun 14, 2015 at 17:03

Andrew Kozin

1,0229 silver badges17 bronze badges

4 Comments

Richard Hamilton Over a year ago

That wouldn't work, because you can have more than one of the same value

Andrew Kozin Over a year ago

ah, sorry. i misunderstood the problem. just a moment. I'll update it

Andrew Kozin Over a year ago

updated. what is interesting, I haven't known about count(i) before :)

Cary Swoveland Over a year ago

Excellent! Best answer so far, imo, but I would suggest a slight simplification: arr1.uniq.reduce(0) { |t,e| t+[arr1.count(e), arr2.count(e)].min }.

Community · Accepted Answer · 2017-05-23 12:04:03Z

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

edited May 23, 2017 at 12:04

CommunityBot

11 silver badge

answered Jun 14, 2015 at 18:04

Cary Swoveland

111k6 gold badges69 silver badges105 bronze badges

Comments

Wayne Conrad · Accepted Answer · 2015-06-15 17:22:24Z

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

edited Jun 15, 2015 at 17:22

answered Jun 15, 2015 at 17:17

Wayne Conrad

109k26 gold badges158 silver badges195 bronze badges

1 Comment

Joe Balsamo Over a year ago

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] # => #<Set: {:b, :c, :a}> Multiset[:a,:b,:c,:b,:b,:c] # => #<Multiset:#3 :b, #2 :c, #1 :a> Multisets are typically used for counting elements and their appearances in collections. Very interesting. Thank you for making me aware of this gem.

MrTheWalrus · Accepted Answer · 2015-06-14 19:55:18Z

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.

edited Jun 14, 2015 at 19:55

answered Jun 14, 2015 at 17:08

MrTheWalrus

9,7102 gold badges44 silver badges67 bronze badges

7 Comments

Richard Hamilton Over a year ago

You forgot a closing ] in matches +=` line

MrTheWalrus Over a year ago

Thanks, yeah, I'm just throwing this together off the top of my head, so there might be syntax issues.

Richard Hamilton Over a year ago

I tried this in irb. Now I'm getting undefined method '+' for nil:Nilclass

MrTheWalrus Over a year ago

There we go. Should have gotten my code working before answering, but I think it's working now.

Cary Swoveland Over a year ago

Your method count is sometimes called a "counting hash" and is conventionally written, def count(arr); arr.each_with_object(Hash.new(0)) { |e,h| h[e] += 1 }; end.

|

Collectives™ on Stack Overflow

Counting matching elements in an array

5 Answers 5

6 Comments

4 Comments

Comments

1 Comment

7 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

6 Comments

4 Comments

Comments

1 Comment

7 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related