Распределение целых чисел с использованием весов? Как рассчитать?

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

У меня есть код Python, чтобы продемонстрировать, что я пытаюсь сделать, и проблема:

def distribute(total, distribution):
 distributed_total = []
 for weight in distribution:
 weight = float(weight)
 p = weight/sum(distribution)
 weighted_value = round(p*total)
 distributed_total.append(weighted_value)
 return distributed_total
for x in xrange(100):
 d = distribute(x, (1,2,3))
 if x != sum(d):
 print x, sum(d), d

Есть много случаев, показанных вышеприведенным кодом, где распределение значения приводит к тому, что сумма распределения отличается от исходного значения. Например, распределение 3 с весами (1,2,3) приводит к (1,1,2), что составляет 4.

Каков самый простой способ исправить этот алгоритм распространения?

UPDATE:

Я ожидаю, что распределенные значения будут целыми. Не имеет значения, как распределяются целые числа, пока они соответствуют правильному значению, и они "максимально приближены" к правильному распределению.

(По правильному распределению я имею в виду нецелое распределение, и я не полностью определил, что я подразумеваю под "как можно ближе". Возможно, существует несколько допустимых выходов, если они суммируют исходное значение.)

4 ответа

Распределите первую часть, как ожидалось. Теперь у вас есть более простая проблема с одним меньшим количеством участников и уменьшенной суммой, доступной для распространения. Повторяйте, пока участников больше не будет.

>>> def distribute2(available, weights):
... distributed_amounts = []
... total_weights = sum(weights)
... for weight in weights:
... weight = float(weight)
... p = weight / total_weights
... distributed_amount = round(p * available)
... distributed_amounts.append(distributed_amount)
... total_weights -= weight
... available -= distributed_amount
... return distributed_amounts
...
>>> for x in xrange(100):
... d = distribute2(x, (1,2,3))
... if x != sum(d):
... print x, sum(d), d
...
>>>


Вы должны как-то распространять ошибки округления:

Actual:
| | | |
Pixel grid:
| | | |

Простейшим было бы округлить каждое истинное значение до ближайшего пикселя, как для начальной, так и для конечной позиции. Итак, когда вы округлите блок A 0,5 до 1, вы также измените начальную позицию блока B от 0,5 до 1. Это уменьшает размер B на 0,5 (по сути, "крадя" размер от него). Разумеется, это приводит к тому, что B имеет размер Steal от C, что в конечном итоге приводит к:

| | | |

но как еще вы ожидали разделить 3 на 3 интегральные части?


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

def distribute(total, weights):
 scale = float(sum(weights))/total
 return [x/scale for x in weights]


Если вы ожидаете, что распределение 3 с весами (1,2,3) будет равно (0,5, 1, 1,5), то округление будет вашей проблемой:

weighted_value = round(p*total)

Вы хотите:

weighted_value = p*total

EDIT: решение для возврата целочисленного распределения

def distribute(total, distribution):
 leftover = 0.0
 distributed_total = []
 distribution_sum = sum(distribution)
 for weight in distribution:
 weight = float(weight)
 leftover, weighted_value = modf(weight*total/distribution_sum + leftover)
 distributed_total.append(weighted_value)
 distributed_total[-1] = round(distributed_total[-1]+leftover) #mitigate round off errors
 return distributed_total

licensed under cc by-sa 3.0 with attribution.