How to optimally distribute values across an array of percentages?
Let's say I have the following code:
arr = [0.1,0.5,0.2,0.2]; //The percentages (or decimals) we want to distribute them over.
value = 100; //The amount of things we have to distribute
arr2 = [0,0,0,0] //Where we want how many of each value to go
To find out how to evenly distribute a hundred over an array, it's simple:
0.1 * 100 = 10 0.5 * 100 = 50 ...
Or do it with a for loop:
for (var i = 0; j < arr.length; i++) {
arr2[i] = arr[i] * value;
}
However, let each counter be an object and therefore must be integer . How can I (as far as I can) distribute them over a different value. Let's say the value is 12.
0.1 * 12 = 1.2 0.5 * 12 = 6 ...
How do I deal with the decimal point when I need it to be solid? Rounding off means that I might not have 12 pieces.
The correct algorithm is
Take input / iteration through an array of values (in this example we will use the array defined above.
Turn it into a set of integers that together add a value (which would be 100 for that)
Print an array of values, which in this example will look something like [10,50,20,20] (they add up to 100, we need to add them, as well as all integers).
If any value is not integer, it must make it integer, so that the entire array will still add up to the required value (100).
TL; DR , which handles decimal places when distributing values across an array and tries to convert them to an integer
Note. ... If this is posted on another stackoverflow website, my programming need is, but the actual question will most likely be solved with math. Also, I had no idea how to phrase this question, which makes it difficult to google it. If I am missing something incredibly obvious, please tell me.
source to share
You must round all values by assigning them using rounding, which is known to distribute rounding evenly. Finally, the last value will be assigned differently to round the amount up 1
.
Let it start slowly, or it's very confusing. First, let's see how to assign the last value to the total of the desired value.
// we will need this later on
sum = 0;
// assign all values but the last
for (i = 0; i < output.length - 1; i++)
{
output[i] = input[i] * total;
sum += output[i];
}
// last value must honor the total constraint
output[i] = total - sum;
This last line needs some explanation. i
will be greater than the last valid int loop for(..)
, so it will be:
output.length - 1 // last index
The value we assign will be such that sum
all elements are equal total
. We have already calculated the sum in one pass when assigning values and therefore do not need to iterate over these elements a second time to determine it.
Next, we'll look at the rounding problem. Let's simplify the above code so that it uses the function we'll talk about shortly:
sum = 0;
for (i = 0; i < output.length - 1; i++)
{
output[i] = u(input[i], total);
sum += output[i];
}
output[i] = total - sum;
As you can see, nothing has changed except the introduction of the function u()
. Now focus on this.
There are several approaches to implementation u()
.
DEFINITION
u(c, total) ::= c * total
By this definition, you get the same as above. That's fine and fine, but as you asked, you want the values to be natural numbers (eG integers). So, although for real numbers this is already ideal, for natural numbers we have to round it up. Let's assume we are using a simple rounding rule for integers:
[ 0.0, 0.5 [ => round down
[ 0.5, 1.0 [ => round up
This is accomplished with:
function u(c, total)
{
return Math.round(c * total);
}
When you are unlucky, you can round (or round) so many values that the last correction of the value will not be enough to meet the overall limit, and usually the whole value will be too large. This is a well-known problem in which there is a multidimensional solution for drawing lines in 2D and 3D space called the Bresenham algorithm .
To keep things simple, I'll show you how to implement it in 1 dimension (which is your case).
Let the term be discussed first: the remainder. This is what's left after rounding up your numbers. It is calculated as the difference between what you want and what you actually have:
DEFINITION
WISH ::= c * total
HAVE ::= Math.round(WISH)
REMAINDER ::= WISH - HAVE
Now think about it. The leftover is like a piece of paper that you discard when you cut the shape out of the sheet. This leftover paper is still there, but you throw it away. Instead, just add it to the next cutout so it doesn't go to waste:
WISH ::= c * total + REMAINDER_FROM_PREVIOUS_STEP
HAVE ::= Math.round(WISH)
REMAINDER ::= WISH - HAVE
This way you save the error and carry it to the next section in your calculation. This is called error amortization.
Here's an amortized implementation u()
:
// amortized is defined outside u because we need to have a side-effect across calls of u
function u(c, total)
{
var real, natural;
real = c * total + amortized;
natural = Math.round(real);
amortized = real - natural;
return natural;
}
At your discretion, you can have a different rounding rule like Math.floor()
or Math.ceil()
.
I would advise you to use Math.floor()
it because it has been checked correctly with full constraint. As you use Math.round()
, you will have smoother cushioning, but you risk not having the last positive value. You might end up with something like this:
[ 1, 0, 0, 1, 1, 0, -1 ]
Only when ALL VALUES are far from 0
can you be sure that the last value will also be positive. So, in general, Bresenham's algoritm algorithm will use flooring, resulting in this latter implementation:
function u(c, total)
{
var real, natural;
real = c * total + amortized;
natural = Math.floor(real); // just to be on the safe side
amortized = real - natural;
return natural;
}
sum = 0;
amortized = 0;
for (i = 0; i < output.length - 1; i++)
{
output[i] = u(input[i], total);
sum += output[i];
}
output[i] = total - sum;
Obviously, the array input
and output
must have the same size, and the values in input
must be parity (sum up to 1).
This type of algorithm is very common for probabilistic and statistical computing.
source to share