Ruby array subtraction without removing items more than once

Question

The canonical Array difference example in Ruby is:

[ 1, 1, 2, 2, 3, 3, 4, 5 ] - [ 1, 2, 4 ]  #=>  [ 3, 3, 5 ]

What's the best way to get the following behavior instead?

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

That is, only the first instance of each matching item in the second array is removed from the first array.

Answer 1

This is all I can think of so far:

[1, 2, 4].each { |x| ary.delete_at ary.index(x) }

Answer 2

In O(n log m + m log m) time:

require 'set'

class Array
  def subtract_once(*values)
    values = Set.new values 
    reject { |e| values.include?(e) && values.delete(e) }
  end
end

Answer 3

class Array
  def subtract_once(b)
    h = b.inject({}) {|memo, v|
      memo[v] ||= 0; memo[v] += 1; memo
    }
    reject { |e| h.include?(e) && (h[e] -= 1) >= 0 }
  end
end

I believe this does what I want. Many thanks to @glebm