Как округлить числа с плавающей точкой до целых при сохранении их суммы

Question

Допустим, у меня есть массив чисел с плавающей запятой в отсортированном (скажем, возрастающем) порядке, сумма которого, как известно, является целым числом N. Я хочу округлить эти числа до целых, оставив их сумму без изменений. Другими словами, я ищу алгоритм, который преобразует массив чисел с плавающей запятой (назовем его fn) в массив целых чисел (назовем его in), такой что:

1. оба массива имеют одинаковую длину
2. сумма массива целых чисел равна N
3. разница между каждым числом с плавающей точкой fn[i] и соответствующим ему целым числом in[i] меньше 1 (или равна 1, если вам действительно нужно)
4. учитывая, что числа с плавающей точкой расположены в отсортированном порядке (fn[i] <= fn[i+1]), целые числа также будут в отсортированном порядке (in[i] <= in[i+1])

Учитывая, что эти четыре условия выполнены, алгоритм, который минимизирует дисперсию округления (sum((in[i] - fn[i])^2)), является предпочтительным, но это не имеет большого значения.

Примеры:

[0.02, 0.03, 0.05, 0.06, 0.07, 0.08, 0.09, 0.1, 0.11, 0.12, 0.13, 0.14]
    => [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
[0.1, 0.3, 0.4, 0.4, 0.8]
    => [0, 0, 0, 1, 1]
[0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1]
    => [0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
[0.4, 0.4, 0.4, 0.4, 9.2, 9.2]
    => [0, 0, 1, 1, 9, 9] is preferable
    => [0, 0, 0, 0, 10, 10] is acceptable
[0.5, 0.5, 11]
    => [0, 1, 11] is fine
    => [0, 0, 12] is technically not allowed but I'd take it in a pinch

Чтобы ответить на несколько прекрасных вопросов, поднятых в комментариях:

• Повторные элементы разрешены в обоих массивах (хотя мне также было бы интересно услышать об алгоритмах, которые работают, только если массив с плавающей точкой не содержит повторов)
• Единого правильного ответа не существует - для данного входного массива чисел с плавающей запятой обычно существует несколько массивов целых чисел, которые удовлетворяют четырем условиям.
• Приложение, которое я имел в виду, было - и это довольно странно - распределять очки между лучшими финишерами в игре MarioKart ;-) На самом деле я никогда не играл в эту игру, но, наблюдая за кем-то еще, я заметил, что их было 24. очки распределялись между четырьмя лучшими финишерами, и я удивлялся, как можно распределить очки по времени финиша (поэтому, если кто-то финиширует с большим отрывом, он получает большую долю очков). В игре отслеживаются итоговые значения в виде целых чисел, поэтому возникает необходимость в таком округлении.

---

Для любопытных вот тестовый скрипт Я использовал, чтобы определить, какие алгоритмы работали.

Answer 1

Один из вариантов, который вы можете попробовать, это "каскадное округление".

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

number  running total   integer integer running total
   1.3       1.3          1           1
   1.7       3.0          2           3
   1.9       4.9          2           5
   2.2       8.1          3           8
   2.8      10.9          3          11
   3.1      14.0          3          14

Answer 2

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

Язык - это некий псевдоязык, который, вероятно, основан на JavaScript или Lua. Должен объяснить суть. Обратите внимание на индексирование, основанное на одном (что лучше для циклов от x до y: p)

// Temp array with same length as fn.
tempArr = Array(fn.length)

// Calculate the expected sum.
arraySum = sum(fn)

lowerSum = 0
-- Populate temp array.
for i = 1 to fn.lengthf
    tempArr[i] = { result: floor(fn[i]),              // Lower bound
                   difference: fn[i] - floor(fn[i]),  // Roundoff error
                   index: i }                         // Original index

    // Calculate the lower sum
    lowerSum = lowerSum + tempArr[i].result
end for

// Sort the temp array on the roundoff error
sort(tempArr, "difference")

// Now arraySum - lowerSum gives us the difference between sums of these
// arrays. tempArr is ordered in such a way that the numbers closest to the
// next one are at the top.
difference = arraySum - lowerSum

// Add 1 to those most likely to round up to the next number so that
// the difference is nullified.
for i = (tempArr.length - difference + 1) to tempArr.length
    tempArr.result = tempArr.result + 1
end for

// Optionally sort the array based on the original index.
array(sort, "index")

Answer 3

Один действительно простой способ - взять все дробные части и суммировать их. Это число по определению вашей проблемы должно быть целым числом. Распределите это целое число равномерно, начиная с наибольшего из ваших чисел. Затем дайте одно второму по величине числу ... и т. Д., Пока не закончится что-то распространять.

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

float accumulator = 0;

for (i = 0; i < num_elements; i++)  /* assumes 0 based array */
{
   accumulator += (fn[i] - floor(fn[i])); 
   fn[i] =  (fn[i] - floor(fn[i]);
}

i = num_elements;

while ((accumulator > 0) && (i>=0))
{
    fn[i-1] += 1;   /* assumes 0 based array */
    accumulator -= 1;
    i--;
}

Обновление: Существуют другие методы распределения накопленных значений в зависимости от того, сколько усечения было выполнено для каждого значения. Это потребует сохранения отдельного списка под названием loss [i] = fn [i] - floor (fn [i]). Затем вы можете повторить список fn [i] и повторно присвоить 1 элементу наибольших потерь (затем установите для потерь [i] значение 0). Это сложно, но я думаю, что это работает.

Answer 4

Как насчет:

a) start: array is [0.1, 0.2, 0.4, 0.5, 0.8], N=3, presuming it's sorted
b) round them all the usual way: array is [0 0 0 1 1]
c) get the sum of the new array and subtract it from N to get the remainder.
d) while remainder>0, iterate through elements, going from the last one
   - check if the new value would break rule 3.
   - if not, add 1
e) in case that remainder<0, iterate from first one to the last one
   - check if the new value would break rule 3.
   - if not, subtract 1

Answer 5

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

1. Округляйте числа с плавающей точкой, как обычно, но следите за тем, чтобы дельта не округлялась и связанный индекс в fn и in.
2. Сортировка второго массива по дельте.
3. Пока sum(in) < N, работать вперед от наибольшей отрицательной дельты, увеличивая округленное значение (убедившись, что вы все еще удовлетворяете правилу № 3).
4. Или, пока sum(in) > N, работать в обратном направлении от наибольшей положительной дельты, уменьшая округленное значение (убедившись, что вы все еще удовлетворяете правилу № 3).

Пример:

[0.02, 0.03, 0.05, 0.06, 0.07, 0.08, 0.09, 0.1, 0.11, 0.12, 0.13, 0.14] N=1

1. [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] sum=0
and [[-0.02, 0], [-0.03, 1], [-0.05, 2], [-0.06, 3], [-0.07, 4], [-0.08, 5], 
     [-0.09, 6], [-0.1, 7], [-0.11, 8], [-0.12, 9], [-0.13, 10], [-0.14, 11]]

2. sorting will reverse the array

3. working from the largest negative remainder, you get [-0.14, 11].
Increment `in[11]` and you get [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1] sum=1 
Done.

Answer 6

Проблема, на мой взгляд, заключается в том, что алгоритм сортировки не указан. Или больше похоже - стабильная сортировка или нет.

Рассмотрим следующий массив с плавающей точкой:

[0,2 0,2 ​​0,2 ​​0,2 ​​0,2]

Сумма равна 1. Целочисленный массив тогда должен быть:

[0 0 0 0 1]

Однако, если алгоритм сортировки не стабилен, он может отсортировать «1» где-нибудь еще в массиве ...

Answer 7

Ну, 4 - это болевая точка. В противном случае вы можете сделать такие вещи, как «обычно округлять и накапливать остаток; округлять при накоплении> = 1». (редактировать: на самом деле, это все еще может быть в порядке, если вы поменялись местами?)

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

В качестве примера линейного программирования - на примере [1.3, 1.7, 1.9, 2.2, 2.8, 3.1] вы можете иметь правила:

1 <= i < 2
1 <= j < 2
1 <= k < 2
2 <= l < 3
3 <= m < 4
i <= j <= k <= l <= m
i + j + k + l + m = 13

Затем примените некоторую линейную / матричную алгебру ;-p Подсказка: есть продукты для выполнения вышеизложенного, основанные на таких вещах, как алгоритм «Симплекс». Обычный университетский корм (я написал один в универе для своего финального проекта).

Answer 8

Можешь попробовать что-нибудь подобное?

in [i] = fn [i] - int (fn [i]);
fn_res [i] = fn [i] - in [i];

fn_res → - результирующая дробь. (Я думал, что это было основным ...), мы что-то упустили?

Answer 9

Если вы можете принять небольшое изменение в итоговом значении при улучшении дисперсии, это вероятностно сохранит итоговые значения в python:

import math
import random
integer_list = [int(x) + int(random.random() <= math.modf(x)[0]) for x in my_list]

, чтобы объяснить это, округляет все числа и добавляет одно с вероятностью, равной дробной части, то есть один из десяти 0.1 станет 1, а остальные 0

это работает для статистических данных, где вы конвертируете большое количество дробных чисел либо в 1 человека, либо в 0 человек

Answer 10

Не сводя к минимуму дисперсию, вот тривиальная:

1. Сортировка значений слева направо.
2. Округлить все до следующего целого числа.
3. Пусть сумма этих целых чисел равна K. Увеличьте N-K крайних правых значений на 1.
4. Восстановить исходный заказ.

Это, очевидно, удовлетворяет вашим условиям 1.-4. Кроме того, вы можете округлить до ближайшего целого числа и увеличить N-K из тех, которые вы округлили в меньшую сторону. Вы можете сделать это жадно путем разницы между исходным и округленным значением, но каждый цикл округленных значений должен увеличиваться только справа налево, чтобы сохранить отсортированный порядок.