Quantizing an array so that a subset of quantized values is still consistently quantized

Question

Given an array of ints I want to quantize each value so that the sum of quantized values is 100. Each quantized value should also be an integer. This works when the whole array is quantized, but when a subset of quantized values is added up it doesn't remain quantized with respect to the rest of the values.

For example, the values 44, 40, 7, 2, 0, 0 are quantized to 47, 43, 8, 2, 0, 0 (the sum of which is 100). If you take the last 4 quantized values the sum is 53 which is consistent with the first value (i.e. 47 + 53 = 100).

But with the values 78, 7, 7, 1, 0, 0, the sum of the last 4 quantized values (8, 8, 1, 0, 0) is 17. The first quantized value is 84 which when added to 17 does not equal 100. Clearly the reason for this is due to the rounding. Is there a way to adjust the rounding so that subsets are still consistent?

Here is the Ruby code:

class Quantize
  def initialize(array)
    @array = array.map { |a| a.to_i }
  end

  def values
    @array.map { |a| quantize(a) }
  end

  def sub_total(i, j)
    @array[i..j].map { |a| quantize(a) }.reduce(:+)
  end

  private

  def quantize(val)
    (val * 100.0 / total).round(0)
  end

  def total
    @array.reduce(:+)
  end
end

And the (failing) tests:

require 'quantize'

describe Quantize do
  context 'first example' do
    let(:subject) { described_class.new([44, 40, 7, 2, 0, 0]) }

    context '#values' do
      it 'quantizes array to add up to 100' do
        expect(subject.values).to eq([47, 43, 8, 2, 0, 0])
      end
    end

    context '#sub_total' do
      it 'adds a subset of array' do
        expect(subject.sub_total(1, 5)).to eq(53)
      end
    end
  end

  context 'second example' do
    let(:subject) { described_class.new([78, 7, 7, 1, 0, 0]) }

    context '#values' do
      it 'quantizes array to add up to 100' do
        expect(subject.values).to eq([84, 8, 8, 1, 0, 0])
      end
    end

    context '#sub_total' do
      it 'adds a subset of array' do
        expect(subject.sub_total(1, 5)).to eq(16)
      end
    end
  end
end

Answer 1

As noted in the comments on the question, the quantization routine does not perform correctly: the second example [78, 7, 7, 1, 0, 0] is quantized as [84, 8, 8, 1, 0, 0] — which adds to 101 and not to 100.

Here is an approach that will yield correct results:

def quantize(array, value)
  quantized = array.map(&:to_i)
  total = array.reduce(:+)
  remainder = value - total

  index = 0

  if remainder > 0
    while remainder > 0 
      quantized[index] += 1
      remainder -= 1
      index = (index + 1) % quantized.length
    end
  else
    while remainder < 0 
      quantized[index] -= 1
      remainder += 1
      index = (index + 1) % quantized.length
    end
  end

  quantized
end

This solves your problem, as stated in the question. The troublesome result becomes [80, 8, 8, 2, 1, 1], which adds to 100 and maintains the subset relationship that you described. The solution can, of course, be made more performant — but it has the advantage of working and being dead simple to understand.