Вычитание массива Ruby без удаления элементов более одного раза

Question

Пример разности канонических массивов в Ruby:

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

Какой лучший способ получить следующее поведение вместо этого?

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

То есть только первый экземпляр каждого соответствующего элемента во втором массиве удаляется из первого массива.

Answer 1

Вычитайте значения столько раз, сколько они появляются в другом массиве, или любые Перечисляемые :

class Array
  # Subtract each passed value once:
  #   %w(1 2 3 1).subtract_once %w(1 1 2) # => ["3"]
  #   [ 1, 1, 2, 2, 3, 3, 4, 5 ].subtract_once([ 1, 2, 4 ]) => [1, 2, 3, 3, 5]
  # Time complexity of O(n + m)
  def subtract_once(values)
    counts = values.inject(Hash.new(0)) { |h, v| h[v] += 1; h }
    reject { |e| counts[e] -= 1 unless counts[e].zero? }
  end

Вычитайте каждое уникальное значение один раз:

require 'set'
class Array
  # Subtract each unique value once:
  #   %w(1 2 2).subtract_once_uniq %w(1 2 2) # => [2]
  # Time complexity of O((n + m) * log m)
  def subtract_once_uniq(values)
    # note that set is implemented 
    values_set = Set.new values.to_a 
    reject { |e| values_set.delete(e) if values_set.include?(e) }
  end
end

Answer 2

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

Я верю, что это то, что я хочу. Большое спасибо @ glebm

Answer 3

Это все, что я могу себе представить:

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

Answer 4

Аналогично ответу @ Джереми Рутена, но с учетом того факта, что некоторые элементы могут отсутствовать:

# remove each element of y from x exactly once
def array_difference(x, y)
  ret = x.dup
  y.each do |element|
    if index = ret.index(element)
      ret.delete_at(index)
    end
  end
  ret
end

Этот ответ также не изменит исходный массив, так как он работает, поэтому:

x = [1,2,3]
y = [3,4,5]
z = array_difference(x, y) # => [1,2]
x == [1,2,3]               # => [1,2,3]