algorithm - redondear - redondeo de numeros enteros

¿Cómo redondear los flotantes a números enteros mientras se preserva su suma?

Question

Digamos que tengo una matriz de números de coma flotante, en orden ordenado (digamos ascendente), cuya suma se sabe que es un número entero N Quiero "redondear" estos números a números enteros sin modificar su suma. En otras palabras, estoy buscando un algoritmo que convierta el conjunto de números de coma flotante (llámalo fn ) en una matriz de enteros (llámalo) de tal manera que:

1. las dos matrices tienen la misma longitud
2. la suma de la matriz de enteros es N
3. la diferencia entre cada número de coma flotante fn[i] y su número entero correspondiente in[i] es menor que 1 (o igual a 1 si realmente se debe)
4. dado que los flotantes están en orden ordenado ( fn[i] <= fn[i+1] ), los enteros también estarán ordenados ( in[i] <= in[i+1] )

Dado que se satisfacen esas cuatro condiciones, es preferible un algoritmo que minimice la varianza de redondeo ( sum((in[i] - fn[i])^2) ), pero no es gran cosa.

Ejemplos:

[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

Para responder algunas preguntas excelentes planteadas en los comentarios:

• Se permiten elementos repetidos en ambas matrices (aunque también me interesaría saber sobre algoritmos que funcionan solo si la matriz de flotantes no incluye repeticiones)
• No hay una única respuesta correcta: para una matriz de entrada dada de flotantes, generalmente hay varias matrices de entradas que satisfacen las cuatro condiciones.
• La aplicación que tenía en mente era, y esto es algo extraño, distribuir puntos a los primeros clasificados en un juego de MarioKart ;-) Nunca jugué el juego yo mismo, pero mientras miraba a alguien más noté que había 24 puntos distribuidos entre los primeros 4 finalistas, y me pregunté cómo sería posible distribuir los puntos de acuerdo con el tiempo de finalización (por lo que si alguien termina con una ventaja grande obtienen una mayor proporción de puntos). El juego rastrea los totales de los puntos como enteros, de ahí la necesidad de este tipo de redondeo.

Para los curiosos, aquí está el script de prueba que utilicé para identificar qué algoritmos funcionaron.

Answer 1

¿Puedes probar algo como esto?

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

fn_res → es la fracción resultante. (Pensé que esto era básico ...), ¿nos estamos perdiendo algo?

Answer 2

Aquí hay un algoritmo que debería realizar la tarea. La principal diferencia con otros algoritmos es que este redondea los números en el orden correcto siempre. Minimizando el error de redondeo.

El lenguaje es un pseudo lenguaje que probablemente deriva de JavaScript o Lua. Debería explicar el punto. Tenga en cuenta la indexación basada en uno (que es más agradable con xa y para bucles.: 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

Bueno, 4 es el punto de dolor. De lo contrario, podría hacer cosas como "por lo general, redondee hacia abajo y acumule las sobras, redondee hacia arriba cuando el acumulador> = 1". (editar: ¿en realidad, eso podría estar bien siempre y cuando cambies su posición?)

¿Podría haber una manera de hacerlo con programación lineal? (Eso es "programación" matemática, no programación de computadora; necesitaría algunas matemáticas para encontrar la solución factible, aunque probablemente podría omitir la parte habitual de "optimización").

Como ejemplo de la programación lineal, con el ejemplo [1.3, 1.7, 1.9, 2.2, 2.8, 3.1] podría tener las reglas:

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

A continuación, aplique algo de álgebra lineal / de matriz ;-p Sugerencia: hay productos para hacer lo anterior basados ​​en cosas como el algoritmo "Simplex". Forraje universitario común, también (escribí uno en la universidad para mi proyecto final).

Answer 4

Calcule la sum of floor y la sum of numbers . sum of numbers redonda sum of numbers y resta con sum of floor , la diferencia es cuántos cielos tenemos que parchar (cuántos +1 necesitamos). Ordenando la matriz con su diferencia de techo a número, de pequeño a grande.

Para los tiempos de diff (la diff es la cantidad de cielorrasos que necesitamos parchar), establecemos el resultado como el ceiling of number . Otros establecen el resultado como el 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 5

Debajo de una implementación de python y numpy del código de @ mikko-rantanen. Me llevó un poco unir esto, así que esto puede ser útil para futuros Googlers a pesar de la antigüedad del tema.

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 6

El problema, según lo veo, es que el algoritmo de clasificación no está especificado. O más, si es un tipo estable o no.

Considere la siguiente matriz de flotadores:

[0.2 0.2 0.2 0.2 0.2]

La suma es 1. La matriz de enteros debería ser:

[0 0 0 0 1]

Sin embargo, si el algoritmo de clasificación no es estable, podría ordenar el "1" en otro lugar en la matriz ...

Answer 7

Esencialmente, lo que harías sería distribuir las sobras después del redondeo a los candidatos más probables.

1. Redondee los flotadores como lo haría normalmente, pero mantenga un registro del delta del redondeo y del índice asociado en fn y in .
2. Ordenar la segunda matriz por delta.
3. Mientras sum(in) < N , avanza desde el delta negativo más grande, incrementando el valor redondeado (asegurándose de que todavía cumple con la regla n. ° 3).
4. O bien, mientras sum(in) > N , retrocede desde el delta positivo más grande, disminuyendo el valor redondeado (asegúrate de cumplir la regla n. ° 3).

Ejemplo:

[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 8

Haga que las diferencias sumadas sean menores de 1, y verifique que se clasifiquen. algo como,

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++]);
}

(es código de papel, así que no verifiqué la validez).

Answer 9

Qué tal si:

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 10

Sin minimizar la varianza, aquí hay una trivial:

1. Ordenar valores de izquierda a derecha.
2. Redondea todo al siguiente entero.
3. Deje que la suma de esos enteros sea K. Aumente los valores NK más a la derecha en 1.
4. Restaurar el orden original.

Esto obviamente satisface tus condiciones 1.-4. Alternativamente, puede redondear al entero más cercano e incrementar NK de los redondeados. Puede hacer esto con avidez por la diferencia entre el valor original y el redondeado, pero cada ejecución de valores redondeados solo debe aumentarse de derecha a izquierda para mantener el orden ordenado.

Answer 11

Una manera realmente fácil es tomar todas las partes fraccionarias y resumirlas. Ese número según la definición de su problema debe ser un número entero. Distribuya ese número completo de manera uniforme empezando por el número más grande. Luego, dé uno al segundo número más grande ... etc. hasta que se quede sin cosas para distribuir.

Tenga en cuenta que esto es pseudocódigo ... y puede estar apagado por uno en un índice ... es tarde y tengo sueño.

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--;
}

Actualización: hay otros métodos de distribución de los valores acumulados en función de la cantidad de truncamiento que se realizó en cada valor. Esto requeriría mantener una lista separada llamada pérdida [i] = fn [i] - piso (fn [i]). Luego puede repetir sobre la lista fn [i] y dar 1 al elemento de mayor pérdida repetidamente (estableciendo la pérdida [i] a 0 después). Es complicado pero supongo que funciona.

Answer 12

Una opción que podrías probar es "redondear en cascada".

Para este algoritmo, realiza un seguimiento de dos totales acumulados: uno de los números de punto flotante hasta ahora y uno de los enteros hasta el momento. Para obtener el siguiente entero, agregue el siguiente número fp a su total acumulado, redondee el total acumulado, luego resta el total total acumulado del total acumulado redondeado: -

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