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

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

Рассчитать sum of floor и sum of numbers. Округлите sum of numbers и вычтите с sum of floor, разница в том, сколько потолков нам нужно исправить (сколько +1 нам нужно). Сортировка массива с разницей от потолка до номера, от малого к большому.

Для diff раз (diff - это количество потолка, которое нужно исправить), мы устанавливаем результат как ceiling of number. Другие устанавливают результат как floor of numbers.

public class Float_Ceil_or_Floor {

public static int[] getNearlyArrayWithSameSum(double[] numbers) {

    NumWithDiff[] numWithDiffs = new NumWithDiff[numbers.length];
    double sum = 0.0;
    int floorSum = 0;
    for (int i = 0; i < numbers.length; i++) {
        int floor = (int)numbers[i];
        int ceil = floor;
        if (floor < numbers[i]) ceil++; // check if a number like 4.0 has same floor and ceiling
        floorSum += floor;
        sum += numbers[i];
        numWithDiffs[i] = new NumWithDiff(ceil,floor, ceil - numbers[i]);
    }

    // sort array by its diffWithCeil
    Arrays.sort(numWithDiffs, (a,b)->{
        if(a.diffWithCeil < b.diffWithCeil)  return -1;
        else return 1;
    });

    int roundSum = (int) Math.round(sum);
    int diff = roundSum - floorSum;
    int[] res = new int[numbers.length];

    for (int i = 0; i < numWithDiffs.length; i++) {
        if(diff > 0 && numWithDiffs[i].floor != numWithDiffs[i].ceil){
            res[i] = numWithDiffs[i].ceil;
            diff--;
        } else {
            res[i] = numWithDiffs[i].floor;
        }
    }
    return res;
}
public static void main(String[] args) {
    double[] arr = { 1.2, 3.7, 100, 4.8 };
    int[] res = getNearlyArrayWithSameSum(arr);
    for (int i : res) System.out.print(i + " ");

}

}

class NumWithDiff {
    int ceil;
    int floor;
    double diffWithCeil;
    public NumWithDiff(int c, int f, double d) {
        this.ceil = c;
        this.floor = f;
        this.diffWithCeil = d;
    }
}

Answer 2

Ниже python и numpy реализация кода @ mikko-rantanen. Мне понадобилось немного времени, чтобы собрать это воедино, так что это может быть полезно для будущих пользователей Google, несмотря на возраст темы.

import numpy as np
from math import floor

original_array = np.array([1.2, 1.5, 1.4, 1.3, 1.7, 1.9])

# Calculate length of original array
# Need to substract 1, as indecies start at 0, but product of dimensions
# results in a count starting at 1
array_len = original_array.size - 1 # Index starts at 0, but product at 1

# Calculate expected sum of original values (must be integer)
expected_sum = np.sum(original_array)

# Collect values for temporary array population
array_list = []
lower_sum = 0
for i, j in enumerate(np.nditer(original_array)):
    array_list.append([i, floor(j), j - floor(j)]) # Original index, lower bound, roundoff error
# Calculate the lower sum of values
lower_sum += floor(j)

# Populate temporary array
temp_array = np.array(array_list)

# Sort temporary array based on roundoff error
temp_array = temp_array[temp_array[:,2].argsort()]

# Calculate difference between expected sum and the lower sum
# This is the number of integers that need to be rounded up from the lower sum
# The sort order (roundoff error) ensures that the value closest to be
# rounded up is at the bottom of the array
difference = int(expected_sum - lower_sum)

# Add one to the number most likely to round up to eliminate the difference
temp_array_len, _ = temp_array.shape
for i in xrange(temp_array_len - difference, temp_array_len):
    temp_array[i,1] += 1

# Re-sort the array based on original index
temp_array = temp_array[temp_array[:,0].argsort()]

# Return array to one-dimensional format of original array
array_list = []
for i in xrange(temp_array_len):
    array_list.append(int(temp_array[i,1]))
new_array = np.array(array_list)

Answer 3

Сделайте, чтобы суммированные различия были меньше 1, и проверьте, чтобы они были отсортированы. что-то вроде

while(i < sizeof(fn) / sizeof(float)) {
    res += fn[i] - floor(fn[i]);
    if (res >= 1) {
        res--;
        in[i] = ceil(fn[i]);
    }
    else
        in[i] = floor(fn[i]);
    if (in[i-1] > in[i])
        swap(in[i-1], in[i++]);
}

(это бумажный код, поэтому я не проверял действительность.)