Как округлить float до целых чисел, сохраняя их сумму?

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

  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] является предпочтительным
     => [0, 0, 0, 0, 10, 10] приемлемо
 [0,5, 0,5, 11]
     => [0, 1, 11] отлично
     => [0, 0, 12] технически не допускается, но я бы взял его в крайнем случае

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

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

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

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

    Язык – это некоторый псевдоязык, который, вероятно, получен из 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") 

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

    Для этого алгоритма вы отслеживаете два текущих итога: один из чисел с плавающей запятой и один из целых чисел. Чтобы получить следующее целое число, вы добавляете следующий номер 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 

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

    Обратите внимание, что это псевдокод … и может быть отключен одним в индексе … его поздно, и я сон.

     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). Это сложно, но я думаю, это работает.

    Как насчет:

     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 

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

    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
     и [[-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. сортировка приведет к изменению массива
    
     3. работая с наибольшим отрицательным остатком, вы получаете [-0.14, 11].
     Приращение `в [11]` и вы получите [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1] sum = 1 
     Готово. 

    Можете ли вы попробовать что-то вроде этого?

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

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

    Ну, 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. Hint: есть продукты для выполнения вышеизложенного на основе таких вещей, как алгоритм «Simplex». Общий университетский корм, тоже (я написал один в uni для моего финального проекта).

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

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

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

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

    [0 0 0 0 1]

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

    Сделать суммированные различия должны быть ниже 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++]); } 

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

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

     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) 

    Рассчитайте 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; } } 

    Без минимизации дисперсии здесь тривиально:

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

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

    Давайте будем гением компьютера.