Comparing two items in array with Ruby

Question

I'm having trouble with situations in which I need to compare two elements in an array using methods. I find the logic quite simple just using a nested loop but this probably isn't good use of Ruby.

For ex. Determine if array has any pair of 2 numbers that equal 0:

def pairs(array)
  i = 0
  while i < array.length
    y = i + 1
    while y < array.length
      if array[i] + array[y] == 0
        return true
      end
      y += 1
    end
    i += 1
  end
  return false
end

Or if i wanted to see if two things in an array are identical I would use the same logic except set: if array[i] == to array[y]...

Can someone provide a better method to a problem like this?

Answer 1

You are going to like Ruby, in part because you generally won't be using indices to pull out or set the elements of an array.

Here is one way to obtain the desired result. At the end I will present an alternative calculation that could be considered when the array is large.

Code

def pairs(arr)
  arr.map { |e| e < 0 ? -e : e }.
      group_by(&:itself).
      select { |_,v| v.size > 1 }.
      keys
end 

Examples

pairs [1, 8, -2, 12, -15, 5, 3]           #=> []
pairs [1, 8, -2, 12, -15, 5, 3, 2, -3, 1] #=> [1, 2, 3] 

If you want the second example to return [[1, -1], [2, -2], [3, -3]] (though I don't see the point), replace the penultimate line of the method with:

map { |k,_| [k, -k] }

Explanation

The steps for:

arr = [1, 8, -2, 12, -15, 5, 3, 2, -3, 1]

are:

a = arr.map { |e| e < 0 ? -e : e }
  #=> [1, 8, 2, 12, 15, 5, 3, 2, 3, 1] 
b = a.group_by(&:itself)
  #=> {1=>[1, 1], 8=>[8], 2=>[2, 2], 12=>[12], 15=>[15], 5=>[5], 3=>[3, 3]} 

We were given Object#itself in Ruby v2.2. For earlier versions, use:

b = a.group_by { |e| e }

Continuing:

c = b.select { |_,v| v.size > 1 }
  #=> {1=>[1, 1], 2=>[2, 2], 3=>[3, 3]} 
c.keys
  #=> [1, 2, 3] 

The line:

select { |_,v| v.size > 1 }

could be written:

select { |k,v| v.size > 1 }

where k and v represent "key" and "value", but since k is not used in the block calculation it is common practice to replace k with the local variable _ (yes, it's a variable--try it in IRB), mainly to inform the reader that the argument is not being used in the block.

If arr = [1, 1, -1, -1, 2, -2], this will return [1,2]. If you want it to return [1,1,2], you must take a different approach.

Alternative calculation for large arrays

If the array (of size n) is large one can reduce the computational complexity from O(n²) to almost O(n) ("almost" to be explained below) by first converting the array to a set:

require 'set'

arr = [3, 5, -7, 4, 2, 7, -6, 1, 0]
st = arr.to_set
  #=> #<Set: {3, 5, -7, 4, 2, 7, -6, 1, 0}>

We may then compute

arr.find { |n| st.include?(-n) }
  #=> -7

Constucting a set from an array is O(n). Set lookups (st.include?(-n)) are equivalent to hash lookups (i.e., computing h[k] for a given key k), which are nearly constant-time, i.e., O(1).

Answer 2

Often, you can translate the English specification quite directly into Ruby.

In your first question, you ask if any combination of two elements adds to zero. The method to use when you want to know whether something is true for any element of an enumerable is Enumerable#any?. If you want to work on combinations of elements from an array, you use the method Array#combination. For summing, you can use Enumerable#sum, and if you want to know whether a number is zero, you can use Numeric#zero?.

So, a possible implementation of your first question would be:

ary.combination(2).any? { _1.sum.zero? }

Your second question could be answered by this:

ary.combination(2).any? {|a, b| a == b }

In both cases, there are of course other ways to do this. For example, in the first case, we could observe that the only way that two numbers sum to zero is if one is the negative of the other.

Note that none of the things that can typically go wrong in a loop can happen here. No off-by-one errors, no fencepost errors, no wrong terminating condition, no iterating off the end of the array, simply because there is no loop.

Answer 3

Here's my approach to your first question and another method that returns the pairs:

def pairs?(arr)
    arr.inject(false){|c, v| c || (arr.include?(-v) && v > 0)}
end

def get_pairs(arr)
    arr.collect{|val| [val, -val] if arr.include?(-val) && val > 0}.reject(&:nil?)
end

arr = [1, 8, -2, 12, -15, 5, 3]
p pairs?(arr)
p get_pairs(arr)

arr = [1, 8, -2, 12, -15, 5, 3, 2, -3, 1]
p pairs?(arr)
p get_pairs(arr)

Output:

false
[]
true
[[3, -3], [2, -2]]

They don't work when there's a pair of zeros, though. You can handle that case explicitly or perhaps someone could offer a better solution.

Answer 4

If you just want to count an element's occurencies in an array you can use Enumerable#count

a = [1,2,3,4,5,1,2,2]
a.count(2)
# => 3

now if you want to see if there are duplicate entries in an array you can use the uniq method

def has_duplicates?(arr)
  arr.uniq.length == arr.length
end