Many to many order/invoice fitting algorithm

fit_orders.rb

# Order to invoice fitting
#
# @param _orders Order numeric amounts array
# @param _invoices Invoice numeric amounts array
#
def fit_orders(_orders, _invoices)
  _invoices = _invoices.sort

  # find every possible invoice subset match for every order, this should be fast
  orders_and_matches = _orders.map do |order|
    [
      order,
      matching_subsets(order, _invoices).uniq.sort_by(&:length)
    ]
  end

  # print every match
  # orders_and_matches.each { |o, m| puts "#{o} => #{m}" }

  # find the first match combination without collisions
  find_first_fit(orders_and_matches, _invoices)
end

def matching_subsets(_value, _invoices, _index = 0, _set = [])
  results = []

  # prune if value is less than next invoice value (because invoice values are sorted)
  return results if _value < _invoices[_index]

  remaining = _value - _invoices[_index]
  results << (_set + [_invoices[_index]]) if remaining == 0

  if _index + 1 < _invoices.length
    # route 1: use current invoice value
    if remaining > 0
      results += matching_subsets(remaining, _invoices, _index + 1, _set + [_invoices[_index]])
    end

    # route 2: dont use current invoice value
    results += matching_subsets(_value, _invoices, _index + 1, _set)
  end

  return results
end

def find_first_fit(_orders_and_matches, _invoices)
  return [] if _orders_and_matches.empty?

  order, matches = _orders_and_matches.pop

  matches.each do |match|
    remaining_invoices = array_substract(_invoices, match)
    next if remaining_invoices.nil? # collision detected!

    result = find_first_fit(_orders_and_matches.dup, remaining_invoices)
    return result + [[order, match]] unless result.nil?
  end

  return nil
end

def array_substract(_from, _items)
  _from = _from.dup
  _items.each do |x|
    idx = _from.index(x)
    return nil if idx.nil?
    _from.delete_at idx
  end

  _from
end

# Test:

f = [1, 2, 3, 10, 5, 10, 15, 1, 2, 3, 10, 5, 10, 15, 1, 2, 3, 10, 5, 10, 15, 1, 2, 3, 10, 5, 10, 15]
o = [20, 10, 5, 11, 20, 10, 5, 11, 20, 10, 5, 11, 20, 10, 5, 11]

p fit_orders(o, f)
# output: [[20, [2, 3, 15]], [10, [10]], [5, [2, 3]], [11, [1, 10]], [20, [2, 3, 15]], [10, [10]], [5, [2, 3]], [11, [1, 10]], [20, [5, 15]], [10, [10]], [5, [5]], [11, [1, 10]], [20, [5, 15]], [10, [10]], [5, [5]], [11, [1, 10]]]