Выделить массив целых чисел, пропорционально компенсирующих ошибки округления

Question

У меня есть массив неотрицательных значений. Я хочу построить массив значений, сумма которых равна 20, так что они пропорциональны первому массиву.

Это была бы легкая проблема, за исключением того, что я хочу, чтобы пропорциональный массив суммировал точно 20, компенсируя любую ошибку округления.

Например, массив

input = [400, 400, 0, 0, 100, 50, 50] 

даст

output = [8, 8, 0, 0, 2, 1, 1] 
sum(output) = 20 

Однако, в большинстве случаев собираются иметь много ошибок округления, как

input = [3, 3, 3, 3, 3, 3, 18] 

наивности дает

output = [1, 1, 1, 1, 1, 1, 10] 
sum(output) = 16 (ouch) 

Есть ли хороший способ распределить выходной массив так, чтобы он добавлял до 20 каждый раз?

Answer 1

Там очень простой ответ на этот вопрос: Я сделал это много раз. После каждого присваивания в новый массив вы уменьшаете значения, которые вы работаете, следующим образом:

1. Вызвать первый массив A и новый пропорциональный массив B (который начинается пустым).
2. Вызов сумма элементов T
3. вызова желаемой суммы С.
4. Для каждого элемента массива (I), необходимо сделать следующее:
   а. B [i] = round (A [i]/T * S). (округление до ближайшего целого числа, копейки или любого другого)
   b. T = T - A [i]
   c. S = S - B [i]

Вот и все! Легко реализуется на любом языке программирования или в электронной таблице.

Решение является оптимальным в том, что результирующие элементы массива никогда не будут более 1 от их идеальных, не округлых значений. Давайте продемонстрируем с вашим примером:
T = 36, S = 20. B [1] = round (A [1]/T * S) = 2. (в идеале 1.666 ....)
T = 33, S = 18. B [2] = круглый (A [2]/T * S) = 2. (в идеале 1.666 ....)
T = 30, S = 16. B [3] = round (A [3]/T * S) = 2. (в идеале, 1.666 ....)
T = 27, S = 14. B [4] = круглый (A [4]/T * S) = 2. (в идеале 1.666 ....)
T = 24, S = 12. B [5] = круглый (A [5]/T * S) = 2. (в идеале, 1.666 ....)
T = 21, S = 10. B [6] = круглый (A [6]/T * S) = 1. (в идеале 1.666 ....)
T = 18, S = 9.   B [7] = раунд (A [7]/T * S) = 9. (в идеале, 10)

Обратите внимание, что при сопоставлении каждого значения в B с его идеальным значением в круглых скобках разница не превышает 1.

Также интересно отметить, что переупорядочение элементов в массиве может привести к различным соответствующим значениям в результирующем массиве. Я обнаружил, что упорядочение элементов в порядке возрастания является лучшим, потому что это приводит к наименьшему среднему значению разница между фактическим и идеальным.

Answer 2

Наивный решение, которое не выполняет хорошо, но обеспечит правильный результат ...

Написать итератор, который дал массив с восемью целыми числами (candidate) и input массива, выходные индексу элемент, который является самым дальним от пропорциональных других (псевдокод):

function next_index(candidate, input) 
    // Calculate weights 
    for i in 1 .. 8 
     w[i] = candidate[i]/input[i] 
    end for 
    // find the smallest weight 
    min = 0 
    min_index = 0 
    for i in 1 .. 8 
     if w[i] < min then 
      min = w[i] 
      min_index = i 
     end if 
    end for 

    return min_index 
end function 

Тогда просто сделать это

result = [0, 0, 0, 0, 0, 0, 0, 0] 
result[next_index(result, input)]++ for 1 .. 20 

Если оптимального решения нет, оно будет искажаться в начале массива.

Используя подход выше, вы можете уменьшить количество итераций, округляя вниз (как вы это делали в вашем примере), а затем просто использовать подход выше, чтобы добавить то, что было оставлено из-за ошибок округления:

result = <<approach using rounding down>> 
while sum(result) < 20 
    result[next_index(result, input)]++ 

Answer 3

Вы установили 3 несовместимых требования. Целочисленный массив, пропорциональный [1,1,1], не может быть заключен в сумме ровно 20. Вы должны выбрать разрыв одной из требований «сумма к точному 20», «пропорциональный вход» и «целочисленные значения».

Если вы решили нарушить требование для целочисленных значений, используйте плавающие или рациональные числа. Если вы решили разорвать точное требование к сумме, то вы уже решили проблему. Выбирать разрывную пропорцию немного сложнее. Один из подходов, который вы можете предпринять, состоит в том, чтобы выяснить, насколько далеко от вашей суммы, а затем распределить исправления случайным образом через выходной массив.Например, если ваш вход:

[1, 1, 1] 

, то вы могли бы сначала сделать его подвести как можно в то же время пропорционально:

[7, 7, 7] 

и так 20 - (7+7+7) = -1, выберите один элемент для уменьшения случайным образом:

[7, 6, 7] 

Если ошибка была 4, вы бы выбрать один из четырех элементов для увеличения.

Answer 4

Таким образом, ответы и комментарии были полезны ... особенно комментарий об уменьшении суммы от @Frederik.

Решение, которое я придумал, использует тот факт, что для входного массива v сумма (v_i * 20) делится на сумму (v). Таким образом, для каждого значения в v, я mulitply на 20 и делить на сумму. Я сохраняю фактор и накапливаю остаток. Всякий раз, когда аккумулятор больше суммы (v), я добавляю его к значению. Таким образом, мне гарантировано, что все оставшиеся вкатываются в результаты.

Разве это разборчиво? Вот реализация в Python:

def proportion(values, total): 
    # set up by getting the sum of the values and starting 
    # with an empty result list and accumulator 
    sum_values = sum(values) 
    new_values = [] 
    acc = 0 

    for v in values: 
     # for each value, find quotient and remainder 
     q, r = divmod(v * total, sum_values) 

     if acc + r < sum_values: 
      # if the accumlator plus remainder is too small, just add and move on 
      acc += r 
     else: 
      # we've accumulated enough to go over sum(values), so add 1 to result 
      if acc > r: 
       # add to previous 
       new_values[-1] += 1 
      else: 
       # add to current 
       q += 1 
      acc -= sum_values - r 

     # save the new value 
     new_values.append(q) 

    # accumulator is guaranteed to be zero at the end 
    print new_values, sum_values, acc 

    return new_values 

(я добавил улучшение, если аккумулятор> остальное, я увеличиваю предыдущее значение вместо текущего значения)

Answer 5

Ваша проблема похожа на proportional representation, где вы хотите (в вашем случае 20) среди партий пропорционально полученным ими голосам в вашем случае [3, 3, 3, 3, 3, 3, 18]

Существует несколько методов, используемых в разных странах: справиться с проблемой округления. My code ниже использует метод Hagenbach-Bischoff quota, используемый в Швейцарии, который в основном распределяет места, оставшиеся после целочисленного деления на (N + 1) к лицам, которые имеют самый высокий остаток:

def proportional(nseats,votes): 
    """assign n seats proportionaly to votes using Hagenbach-Bischoff quota 
    :param nseats: int number of seats to assign 
    :param votes: iterable of int or float weighting each party 
    :result: list of ints seats allocated to each party 
    """ 
    quota=sum(votes)/(1.+nseats) #force float 
    frac=[vote/quota for vote in votes] 
    res=[int(f) for f in frac] 
    n=nseats-sum(res) #number of seats remaining to allocate 
    if n==0: return res #done 
    if n<0: return [min(x,nseats) for x in res] # see siamii's comment 
    #give the remaining seats to the n parties with the largest remainder 
    remainders=[ai-bi for ai,bi in zip(frac,res)] 
    limit=sorted(remainders,reverse=True)[n-1] 
    #n parties with remainter larger than limit get an extra seat 
    for i,r in enumerate(remainders): 
     if r>=limit: 
      res[i]+=1 
      n-=1 # attempt to handle perfect equality 
      if n==0: return res #done 
    raise #should never happen 

Однако этот метод не всегда дает такое же количество мест для лиц с совершенным равенством, как в вашем случае:

proportional(20,[3, 3, 3, 3, 3, 3, 18]) 
[2,2,2,2,1,1,10]