algorithm - Cómo hacer que los porcentajes redondeados sumen hasta el 100%
math rounding (16)
Considere los cuatro porcentajes a continuación, representados como números float :
13.626332%
47.989636%
9.596008%
28.788024%
-----------
100.000000%
Necesito representar estos porcentajes como números enteros. Si simplemente uso Math.round() , termino con un total de 101%.
14 + 48 + 10 + 29 = 101
Si uso parseInt() , termino con un total de 97%.
13 + 47 + 9 + 28 = 97
¿Qué es un buen algoritmo para representar cualquier número de porcentajes como números enteros mientras se mantiene un total de 100%?
Editar : Después de leer algunos de los comentarios y respuestas, hay claramente muchas maneras de resolver esto.
En mi opinión, para mantenerme fiel a los números, el resultado "correcto" es el que minimiza el error general, definido por cuánto introduciría el redondeo de error en relación con el valor real:
value rounded error decision
----------------------------------------------------
13.626332 14 2.7% round up (14)
47.989636 48 0.0% round up (48)
9.596008 10 4.0% don''t round up (9)
28.788024 29 2.7% round up (29)
En caso de empate (3.33, 3.33, 3.33), se puede tomar una decisión arbitraria (por ejemplo, 3, 4, 3).
Aquí hay una implementación de Python más simple de la respuesta @ varun-vohra:
def apportion_pcts(pcts, total):
proportions = [total * (pct / 100) for pct in pcts]
apportions = [math.floor(p) for p in proportions]
remainder = total - sum(apportions)
remainders = [(i, p - math.floor(p)) for (i, p) in enumerate(proportions)]
remainders.sort(key=operator.itemgetter(1), reverse=True)
for (i, _) in itertools.cycle(remainders):
if remainder == 0:
break
else:
apportions[i] += 1
remainder -= 1
return apportions
Necesitas math , itertools , operator .
Creo que lo siguiente logrará lo que busca
function func( orig, target ) {
var i = orig.length, j = 0, total = 0, change, newVals = [], next, factor1, factor2, len = orig.length, marginOfErrors = [];
// map original values to new array
while( i-- ) {
total += newVals[i] = Math.round( orig[i] );
}
change = total < target ? 1 : -1;
while( total !== target ) {
// Iterate through values and select the one that once changed will introduce
// the least margin of error in terms of itself. e.g. Incrementing 10 by 1
// would mean an error of 10% in relation to the value itself.
for( i = 0; i < len; i++ ) {
next = i === len - 1 ? 0 : i + 1;
factor2 = errorFactor( orig[next], newVals[next] + change );
factor1 = errorFactor( orig[i], newVals[i] + change );
if( factor1 > factor2 ) {
j = next;
}
}
newVals[j] += change;
total += change;
}
for( i = 0; i < len; i++ ) { marginOfErrors[i] = newVals[i] && Math.abs( orig[i] - newVals[i] ) / orig[i]; }
// Math.round() causes some problems as it is difficult to know at the beginning
// whether numbers should have been rounded up or down to reduce total margin of error.
// This section of code increments and decrements values by 1 to find the number
// combination with least margin of error.
for( i = 0; i < len; i++ ) {
for( j = 0; j < len; j++ ) {
if( j === i ) continue;
var roundUpFactor = errorFactor( orig[i], newVals[i] + 1) + errorFactor( orig[j], newVals[j] - 1 );
var roundDownFactor = errorFactor( orig[i], newVals[i] - 1) + errorFactor( orig[j], newVals[j] + 1 );
var sumMargin = marginOfErrors[i] + marginOfErrors[j];
if( roundUpFactor < sumMargin) {
newVals[i] = newVals[i] + 1;
newVals[j] = newVals[j] - 1;
marginOfErrors[i] = newVals[i] && Math.abs( orig[i] - newVals[i] ) / orig[i];
marginOfErrors[j] = newVals[j] && Math.abs( orig[j] - newVals[j] ) / orig[j];
}
if( roundDownFactor < sumMargin ) {
newVals[i] = newVals[i] - 1;
newVals[j] = newVals[j] + 1;
marginOfErrors[i] = newVals[i] && Math.abs( orig[i] - newVals[i] ) / orig[i];
marginOfErrors[j] = newVals[j] && Math.abs( orig[j] - newVals[j] ) / orig[j];
}
}
}
function errorFactor( oldNum, newNum ) {
return Math.abs( oldNum - newNum ) / oldNum;
}
return newVals;
}
func([16.666, 16.666, 16.666, 16.666, 16.666, 16.666], 100); // => [16, 16, 17, 17, 17, 17]
func([33.333, 33.333, 33.333], 100); // => [34, 33, 33]
func([33.3, 33.3, 33.3, 0.1], 100); // => [34, 33, 33, 0]
func([13.25, 47.25, 11.25, 28.25], 100 ); // => [13, 48, 11, 28]
func( [25.5, 25.5, 25.5, 23.5], 100 ); // => [25, 25, 26, 24]
Una última cosa, ejecuté la función usando los números originalmente dados en la pregunta para compararla con la salida deseada
func([13.626332, 47.989636, 9.596008, 28.788024], 100); // => [48, 29, 13, 10]
Esto era diferente a lo que quería la pregunta => [48, 29, 14, 9]. No pude entender esto hasta que miré el margen de error total
-------------------------------------------------
| original | question | % diff | mine | % diff |
-------------------------------------------------
| 13.626332 | 14 | 2.74% | 13 | 4.5% |
| 47.989636 | 48 | 0.02% | 48 | 0.02% |
| 9.596008 | 9 | 6.2% | 10 | 4.2% |
| 28.788024 | 29 | 0.7% | 29 | 0.7% |
-------------------------------------------------
| Totals | 100 | 9.66% | 100 | 9.43% |
-------------------------------------------------
Básicamente, el resultado de mi función en realidad introduce la menor cantidad de error.
Violín here
Dado que ninguna de las respuestas aquí parece resolverlo correctamente, aquí está mi versión semi-ofuscada usando underscorejs :
function foo(l, target) {
var off = target - _.reduce(l, function(acc, x) { return acc + Math.round(x) }, 0);
return _.chain(l).
sortBy(function(x) { return Math.round(x) - x }).
map(function(x, i) { return Math.round(x) + (off > i) - (i >= (l.length + off)) }).
value();
}
foo([13.626332, 47.989636, 9.596008, 28.788024], 100) // => [48, 29, 14, 9]
foo([16.666, 16.666, 16.666, 16.666, 16.666, 16.666], 100) // => [17, 17, 17, 17, 16, 16]
foo([33.333, 33.333, 33.333], 100) // => [34, 33, 33]
foo([33.3, 33.3, 33.3, 0.1], 100) // => [34, 33, 33, 0]
El objetivo del redondeo es generar la menor cantidad de error. Cuando redondeas un único valor, ese proceso es simple y directo y la mayoría de las personas lo entienden fácilmente. Cuando se redondean múltiples números al mismo tiempo, el proceso se torna más complicado: debe definir cómo se combinarán los errores, es decir, qué se debe minimizar.
La respuesta bien votado por Varun Vohra minimiza la suma de los errores absolutos, y es muy simple de implementar. Sin embargo, hay casos extremos que no maneja, ¿cuál debería ser el resultado de redondear 24.25, 23.25, 27.25, 25.25 ? Uno de esos debe redondearse en lugar de hacia abajo. Probablemente solo elegirías arbitrariamente el primero o el último en la lista.
Tal vez sea mejor usar el error relativo en lugar del error absoluto . Redondeando 23.25 hasta 24 lo cambia en 3.2% mientras que al redondear 27.25 hasta 28 solo lo cambia en 2.8%. Ahora hay un claro ganador.
Es posible ajustar esto aún más. Una técnica común es cuadrar cada error, de modo que los errores grandes cuentan desproporcionadamente más que los pequeños. También utilizaría un divisor no lineal para obtener el error relativo; no parece correcto que un error al 1% sea 99 veces más importante que un error al 99%. En el siguiente código he usado la raíz cuadrada.
El algoritmo completo es el siguiente:
- Sume los porcentajes después de redondearlos todos, y reste de 100. Esto le indica cuántos de esos porcentajes se deben redondear en su lugar.
- Genere dos puntajes de error para cada porcentaje, uno cuando se redondea hacia abajo y uno cuando se redondea hacia arriba. Toma la diferencia entre los dos.
- Ordene las diferencias de error producidas arriba.
- Para conocer el número de porcentajes que deben redondearse, tome un artículo de la lista ordenada e incremente el porcentaje redondeado por 1.
Aún puede tener más de una combinación con la misma suma de error, por ejemplo 33.3333333, 33.3333333, 33.3333333 . Esto es inevitable, y el resultado será completamente arbitrario. El código que doy a continuación prefiere redondear los valores de la izquierda.
Poner todo junto en Python se ve así.
def error_gen(actual, rounded):
divisor = sqrt(1.0 if actual < 1.0 else actual)
return abs(rounded - actual) ** 2 / divisor
def round_to_100(percents):
if not isclose(sum(percents), 100):
raise ValueError
n = len(percents)
rounded = [int(x) for x in percents]
up_count = 100 - sum(rounded)
errors = [(error_gen(percents[i], rounded[i] + 1) - error_gen(percents[i], rounded[i]), i) for i in range(n)]
rank = sorted(errors)
for i in range(up_count):
rounded[rank[i][1]] += 1
return rounded
>>> round_to_100([13.626332, 47.989636, 9.596008, 28.788024])
[14, 48, 9, 29]
>>> round_to_100([33.3333333, 33.3333333, 33.3333333])
[34, 33, 33]
>>> round_to_100([24.25, 23.25, 27.25, 25.25])
[24, 23, 28, 25]
>>> round_to_100([1.25, 2.25, 3.25, 4.25, 89.0])
[1, 2, 3, 4, 90]
Como puede ver con el último ejemplo, este algoritmo todavía es capaz de ofrecer resultados no intuitivos. Aunque 89.0 no necesita ningún redondeo, uno de los valores en esa lista debe redondearse; el error relativo más bajo resulta de redondear ese gran valor en lugar de las alternativas mucho más pequeñas.
Esta respuesta originalmente defendía pasar por todas las combinaciones posibles de redondeo arriba / abajo, pero como se señala en los comentarios, un método más simple funciona mejor. El algoritmo y el código reflejan esa simplificación.
Escribí una ayudante de redondeo de la versión C #, el algoritmo es igual a la respuesta de Varun Vohra , espero que ayude.
public static List<decimal> GetPerfectRounding(List<decimal> original,
decimal forceSum, int decimals)
{
var rounded = original.Select(x => Math.Round(x, decimals)).ToList();
Debug.Assert(Math.Round(forceSum, decimals) == forceSum);
var delta = forceSum - rounded.Sum();
if (delta == 0) return rounded;
var deltaUnit = Convert.ToDecimal(Math.Pow(0.1, decimals)) * Math.Sign(delta);
List<int> applyDeltaSequence;
if (delta < 0)
{
applyDeltaSequence = original
.Zip(Enumerable.Range(0, int.MaxValue), (x, index) => new { x, index })
.OrderBy(a => original[a.index] - rounded[a.index])
.ThenByDescending(a => a.index)
.Select(a => a.index).ToList();
}
else
{
applyDeltaSequence = original
.Zip(Enumerable.Range(0, int.MaxValue), (x, index) => new { x, index })
.OrderByDescending(a => original[a.index] - rounded[a.index])
.Select(a => a.index).ToList();
}
Enumerable.Repeat(applyDeltaSequence, int.MaxValue)
.SelectMany(x => x)
.Take(Convert.ToInt32(delta/deltaUnit))
.ForEach(index => rounded[index] += deltaUnit);
return rounded;
}
Pasa la siguiente prueba unitaria:
[TestMethod]
public void TestPerfectRounding()
{
CollectionAssert.AreEqual(Utils.GetPerfectRounding(
new List<decimal> {3.333m, 3.334m, 3.333m}, 10, 2),
new List<decimal> {3.33m, 3.34m, 3.33m});
CollectionAssert.AreEqual(Utils.GetPerfectRounding(
new List<decimal> {3.33m, 3.34m, 3.33m}, 10, 1),
new List<decimal> {3.3m, 3.4m, 3.3m});
CollectionAssert.AreEqual(Utils.GetPerfectRounding(
new List<decimal> {3.333m, 3.334m, 3.333m}, 10, 1),
new List<decimal> {3.3m, 3.4m, 3.3m});
CollectionAssert.AreEqual(Utils.GetPerfectRounding(
new List<decimal> { 13.626332m, 47.989636m, 9.596008m, 28.788024m }, 100, 0),
new List<decimal> {14, 48, 9, 29});
CollectionAssert.AreEqual(Utils.GetPerfectRounding(
new List<decimal> { 16.666m, 16.666m, 16.666m, 16.666m, 16.666m, 16.666m }, 100, 0),
new List<decimal> { 17, 17, 17, 17, 16, 16 });
CollectionAssert.AreEqual(Utils.GetPerfectRounding(
new List<decimal> { 33.333m, 33.333m, 33.333m }, 100, 0),
new List<decimal> { 34, 33, 33 });
CollectionAssert.AreEqual(Utils.GetPerfectRounding(
new List<decimal> { 33.3m, 33.3m, 33.3m, 0.1m }, 100, 0),
new List<decimal> { 34, 33, 33, 0 });
}
Este es un caso para el redondeo del banquero, también conocido como "round half-even". Es compatible con BigDecimal. Su objetivo es garantizar que el redondeo salda, es decir, no favorece ni al banco ni al cliente.
Hay muchas formas de hacer esto, siempre que no esté preocupado por la dependencia de los datos decimales originales.
El primer y tal vez el método más popular sería el método más grande que queda
Que es básicamente:
- Redondeando todo
- Obteniendo la diferencia en suma y 100
- Distribuir la diferencia agregando 1 a los elementos en orden decreciente de sus partes decimales
En tu caso, sería así:
13.626332%
47.989636%
9.596008%
28.788024%
Si tomas las partes enteras, obtienes
13
47
9
28
que suma 97, y desea agregar tres más. Ahora, mira las partes decimales, que son
.626332%
.989636%
.596008%
.788024%
y tome los más grandes hasta que el total llegue a 100. Entonces obtendría:
14
48
9
29
Alternativamente, simplemente puede elegir mostrar un lugar decimal en lugar de valores enteros. Entonces los números serían 48.3 y 23.9, etc. Esto reduciría la varianza de 100 por mucho.
He implementado el método de la respuesta de Varun Vohra aquí para ambas listas y dictados.
import math
import numbers
import operator
import itertools
def round_list_percentages(number_list):
"""
Takes a list where all values are numbers that add up to 100,
and rounds them off to integers while still retaining a sum of 100.
A total value sum that rounds to 100.00 with two decimals is acceptable.
This ensures that all input where the values are calculated with [fraction]/[total]
and the sum of all fractions equal the total, should pass.
"""
# Check input
if not all(isinstance(i, numbers.Number) for i in number_list):
raise ValueError(''All values of the list must be a number'')
# Generate a key for each value
key_generator = itertools.count()
value_dict = {next(key_generator): value for value in number_list}
return round_dictionary_percentages(value_dict).values()
def round_dictionary_percentages(dictionary):
"""
Takes a dictionary where all values are numbers that add up to 100,
and rounds them off to integers while still retaining a sum of 100.
A total value sum that rounds to 100.00 with two decimals is acceptable.
This ensures that all input where the values are calculated with [fraction]/[total]
and the sum of all fractions equal the total, should pass.
"""
# Check input
# Only allow numbers
if not all(isinstance(i, numbers.Number) for i in dictionary.values()):
raise ValueError(''All values of the dictionary must be a number'')
# Make sure the sum is close enough to 100
# Round value_sum to 2 decimals to avoid floating point representation errors
value_sum = round(sum(dictionary.values()), 2)
if not value_sum == 100:
raise ValueError(''The sum of the values must be 100'')
# Initial floored results
# Does not add up to 100, so we need to add something
result = {key: int(math.floor(value)) for key, value in dictionary.items()}
# Remainders for each key
result_remainders = {key: value % 1 for key, value in dictionary.items()}
# Keys sorted by remainder (biggest first)
sorted_keys = [key for key, value in sorted(result_remainders.items(), key=operator.itemgetter(1), reverse=True)]
# Otherwise add missing values up to 100
# One cycle is enough, since flooring removes a max value of < 1 per item,
# i.e. this loop should always break before going through the whole list
for key in sorted_keys:
if sum(result.values()) == 100:
break
result[key] += 1
# Return
return result
NO sume los números redondeados. Tendrás resultados inexactos. El total podría disminuir significativamente según la cantidad de términos y la distribución de partes fraccionarias.
Muestre los números redondeados pero sume los valores reales. Dependiendo de cómo presentas los números, la forma real de hacerlo variaría. De esa manera obtienes
14 48 10 29 __ 100
De cualquier forma que vayas, tendrás discrepancias. No hay forma en su ejemplo de mostrar números que sumen 100 sin "redondear" un valor de la manera incorrecta (el mínimo error estaría cambiando 9.596 a 9)
EDITAR
Debe elegir entre una de las siguientes opciones:
- Exactitud de los artículos
- Exactitud de la suma (si está sumando valores redondeados)
- Consistencia entre los artículos redondeados y la suma redondeada)
La mayor parte del tiempo cuando se trata de porcentajes n. ° 3 es la mejor opción porque es más obvio cuando el total equivale al 101% que cuando los artículos individuales no suman un total de 100, y se mantienen los elementos individuales precisos. "Redondear" 9.596 a 9 es inexacto en mi opinión.
Para explicar esto, a veces agrego una nota al pie que explica que los valores individuales son redondeados y pueden no sumar el 100%. Cualquiera que entienda el redondeo debería ser capaz de entender esa explicación.
No estoy seguro del nivel de precisión que necesita, pero lo que haría sería simplemente agregar 1 los primeros n números, siendo n el límite máximo de la suma total de decimales. En este caso, eso es 3 , así que agregaría 1 a los primeros 3 elementos y pondría el resto en el suelo. Por supuesto, esto no es muy preciso, algunos números pueden redondearse hacia arriba o hacia abajo cuando no debería, pero funciona bien y siempre dará como resultado un 100%.
Entonces [ 13.626332, 47.989636, 9.596008, 28.788024 ] sería [14, 48, 10, 28] porque Math.ceil(.626332+.989636+.596008+.788024) == 3
function evenRound( arr ) {
var decimal = -~arr.map(function( a ){ return a % 1 })
.reduce(function( a,b ){ return a + b }); // Ceil of total sum of decimals
for ( var i = 0; i < decimal; ++i ) {
arr[ i ] = ++arr[ i ]; // compensate error by adding 1 the the first n items
}
return arr.map(function( a ){ return ~~a }); // floor all other numbers
}
var nums = evenRound( [ 13.626332, 47.989636, 9.596008, 28.788024 ] );
var total = nums.reduce(function( a,b ){ return a + b }); //=> 100
Siempre puede informar a los usuarios que los números se redondean y que pueden no ser muy precisos ...
Podría intentar realizar un seguimiento de su error debido al redondeo, y luego redondearlo contra el grano si el error acumulado es mayor que la porción fraccionaria del número actual.
13.62 -> 14 (+.38)
47.98 -> 48 (+.02 (+.40 total))
9.59 -> 10 (+.41 (+.81 total))
28.78 -> 28 (round down because .81 > .78)
------------
100
No estoy seguro de si esto funcionaría en general, pero parece funcionar de manera similar si el orden se revierte:
28.78 -> 29 (+.22)
9.59 -> 9 (-.37; rounded down because .59 > .22)
47.98 -> 48 (-.35)
13.62 -> 14 (+.03)
------------
100
Estoy seguro de que hay casos límite en los que esto podría romperse, pero cualquier enfoque será al menos algo arbitrario ya que básicamente estás modificando tus datos de entrada.
Probablemente la "mejor" forma de hacerlo sea mantener un recuento continuo (no integral) de dónde se encuentra y redondear ese valor, luego usarlo junto con el historial para determinar qué valor se debe usar. Por ejemplo, usando los valores que dio:
Value CumulValue CumulRounded PrevBaseline Need
--------- ---------- ------------ ------------ ----
0
13.626332 13.626332 14 0 14 ( 14 - 0)
47.989636 61.615968 62 14 48 ( 62 - 14)
9.596008 71.211976 71 62 9 ( 71 - 62)
28.788024 100.000000 100 71 29 (100 - 71)
---
100
En cada etapa, no redondeas el número mismo. En cambio, redondea el valor acumulado y calcula el mejor entero que alcanza ese valor desde la línea de base anterior: esa línea base es el valor acumulado (redondeado) de la fila anterior.
Esto funciona porque no está perdiendo información en cada etapa, sino que está utilizando la información de forma más inteligente. Los valores redondeados ''correctos'' están en la columna final y puede ver que suman 100.
Si lo redondeas, no hay una buena manera de obtenerlo exactamente igual en todos los casos.
Puede tomar la parte decimal de los N porcentajes que tiene (en el ejemplo que le dio es 4).
Agregue las partes decimales. En tu ejemplo, tienes un total de parte fraccionaria = 3.
Ceil los 3 números con fracciones más altas y piso el resto.
(Perdón por las ediciones)
Si realmente debe redondearlos, ya hay sugerencias muy buenas aquí (resto más grande, menos error relativo, etc.).
También hay una buena razón para no redondear (obtendrá al menos un número que "se ve mejor" pero está "equivocado"), y cómo resolverlo (avisen a sus lectores) y eso es lo que hago.
Permítanme agregar la parte del número "equivocado".
Supongamos que tiene tres eventos / entidades / ... con algunos porcentajes que se aproximan como:
DAY 1
who | real | app
----|-------|------
A | 33.34 | 34
B | 33.33 | 33
C | 33.33 | 33
Más tarde, los valores cambian ligeramente, a
DAY 2
who | real | app
----|-------|------
A | 33.35 | 33
B | 33.36 | 34
C | 33.29 | 33
La primera tabla tiene el problema ya mencionado de tener un número "incorrecto": 33.34 está más cerca de 33 que de 34.
Pero ahora tienes un error mayor. Comparando el día 2 con el día 1, el valor del porcentaje real para A aumentó, en un 0,01%, pero la aproximación muestra una disminución del 1%.
Ese es un error cualitativo, probablemente bastante peor que el error cuantitativo inicial.
Se podría idear una aproximación para todo el conjunto, pero puede que tenga que publicar datos el primer día, por lo que no sabrá nada sobre el segundo día. Entonces, a menos que realmente, realmente, deba aproximarse, probablemente sea mejor que no.
Una vez escribí una herramienta directa, para encontrar la perturbación mínima de un conjunto de números para que coincida con un objetivo. Era un problema diferente, pero en teoría se podría usar una idea similar aquí. En este caso, tenemos un conjunto de opciones.
Por lo tanto, para el primer elemento, podemos redondearlo a 14 o bajar a 13. El costo (en un sentido de programación de entero binario) de hacerlo es menor para el redondeo que para el redondeo, porque el redondeo requiere mueve ese valor una distancia mayor. Del mismo modo, podemos redondear cada número hacia arriba o hacia abajo, por lo que hay un total de 16 opciones que debemos elegir.
13.626332
47.989636
9.596008
+ 28.788024
-----------
100.000000
Normalmente resolvería el problema general en MATLAB, aquí usando bintprog, una herramienta de programación de enteros binarios, pero solo hay unas pocas opciones para probar, por lo que es bastante fácil con bucles simples para probar cada una de las 16 alternativas. Por ejemplo, supongamos que tuviéramos que redondear este conjunto como:
Original Rounded Absolute error
13.626 13 0.62633
47.99 48 0.01036
9.596 10 0.40399
+ 28.788 29 0.21198
---------------------------------------
100.000 100 1.25266
El error absoluto total realizado es 1.25266. Se puede reducir ligeramente mediante el siguiente redondeo alternativo:
Original Rounded Absolute error
13.626 14 0.37367
47.99 48 0.01036
9.596 9 0.59601
+ 28.788 29 0.21198
---------------------------------------
100.000 100 1.19202
De hecho, esta será la solución óptima en términos del error absoluto. Por supuesto, si hubiera 20 términos, el espacio de búsqueda será de tamaño 2 ^ 20 = 1048576. Por 30 o 40 términos, ese espacio será de un tamaño significativo. En ese caso, necesitaría usar una herramienta que pueda buscar de manera eficiente el espacio, tal vez utilizando un esquema de bifurcación y encuadernación.
compruebe si esto es válido o no en cuanto a mis casos de prueba. Puedo hacerlo funcionar.
digamos que el número es k;
- ordenar el porcentaje al descender oder.
- iterar sobre cada porcentaje desde el orden descendente.
- calcule el porcentaje de k para el primer porcentaje tome Math.Ceil of output.
- siguiente k = k-1
- iterar hasta que se consuma todo el porcentaje.