Find the highest number in a set to be rounded down, and round it up instead

As the title describes, I have a set of objects - call them Allocations - which contain a description & a number. All numbers in the set add up to 100%, but for display purpose I sometimes round to a whole percent. In some edge cases, having rounded the numbers I end up with 99%.

Example:

Description  | Actual | Rounded
===============================
Allocation A | 65.23% | 65% 
Allocation B | 25.40% | 25%
Allocation C | 7.95%  | 8%
Allocation D | 1.42%  | 1%
===============================
Total        | 100%   | 99% (Bad!)

The requested solution, which is imperfect but will do, is to find the highest one to be rounded down, and round it up instead. In the example above, 1.42% would become 2% when rounded. Edit: By "Highest one to be rounded down" 开发者_Python百科I mean the one which is being rounded the furthest. Hence 1.42% is being rounded down by 0.42 whereas the 65.23 is only being rounded down 0.23

So now the code, I have a class

public class Allocation
{
  public string Description {get;set;}
  public doubel Percentage {get;set;}
}

And these are held in an IEnumerable<Allocation>. So, potentially using LINQ, how can I determine which one is the one to round up. Or more specifically, how can I generate a new IEnumerable<Allocation> with the numbers rounded.

If anyone has any other suggestion for always making rounded percentage always equate to 100% that would be even better!

As ho1 has indicated, the solution to add 1 to a specific row doesn't solve the real problem.

Consider these scenarios:

3 items evenly divided, 100/3 = 33 ; 33 * 3 = 99 ; Error = -1
7 items evenly divided, 100/7 = 14 ; 14 * 7 = 98 ; Error = -2
66 items evenly divided, 100/66 = 2 ; 2 * 66 = 132 ; Error = 32

Here's some untested code that might get you close to where you need to go. There's probably a sign error in here so watch out.

public class AllocationRoundingWrapper
{
  public Allocation Original {get;set;}
  public double Rounded {get;set;}
  public double IntroducedError()
  {
    return  Rounded - Original.Percentage;
  }
}

  //project the Allocations into Wrappers for rounding efforts.

List<Allocation> source = GetAllocations();

List<AllocationRoundingWrapper> roundingWrappers = source
  .Select(a => new AllocationRoundingWrapper()
  {
    Original = a,
    Rounded = Math.Round(a.Percentage)
  }).ToList();

int error = (int) roundingWrappers.Sum(x => x.IntroducedError());

  //distribute the rounding errors across the
  // items with the absolute largest error.

List<RoundingWrapper> orderedItems = error > 0 ?
  roundingWrappers.OrderByDescending(x => x.IntroducedError()).ToList() :
  roundingWrappers.OrderBy(x => x.IntroducedError()).ToList();

IEnumerator<RoundingWrapper> enumerator = orderedItems.GetEnumerator();

while(error > 0)
{
  enumerator.MoveNext();
  enumerator.Current.Rounded += 1.0;
  error -= 1;
}
while(error < 0)
{
  enumerator.MoveNext();
  enumerator.Current.Rounded -= 1.0;
  error += 1;
}

  //project back into Allocations for the result
List<Allocation> result = roundingWrappers
  .Select(x => new Allocation()
  {
    Description = x.Original.Description,
    Percentage = x.Rounded
  }).ToList();

Note: Ordering by introduced error can result in ties. Consider the 3 items case, only one item will get +1... you may expect that item to be consistently chosen. If consistent results are expected from multiple runs, ties should be broken.

I'd suggest always rounding down, and then if the result is 100-n, round up the numbers with the 'n' largest residuals. That will work for any data. Approaches which round to nearest and then try to adjust the result are apt to be more complicated. I don't think the fact that the allocations, rounded to 0.01%, add up to 100.00% says anything about what's going to happen when they are rounded to the nearest 0.1% or 1%.

Another approach would be to do the initial computation with round-to-nearest, and then if the result doesn't yield 100% divide all numbers by the total percentage and try again. So if the final percentage was 101%, divide all (unrounded) numbers by 1.01 and repeat the round-and-total sequence. This will give slightly different results which one may find more or less desirable. Suppose the numbers are 1.3 1.3 1.3 96.1. When rounded, those total 99. Rounding one of the 1.3's up to 2 would make the total 100, but rounding would distort the value by 53% rather than 23%; by contrast, rounding 96.1 up to 97 would represent about a 0.95% distortion of its value (97 vs 96.1).

Regarding getting 100%, why not run the original calculation once first and see what percentage you get and then you know how many you need to round up vs down by seeing how many percentage points it differs from 100%.

So if you end up with 97%, round 3 numbers up instead of down. Or if you end up with 102%, round the two numbers with the lowest decimals (over 0.5) down instead of up.

 var HighestDown = 
       allocation.Where(a=>Math.Round(a.Percentage) == Math.Floor(a.Percentage)
                 .Max(a=>a.Percentage - Math.Floor(a.Percentage));

  HighestDown.Percentage = Math.Ceiling(HighestDown.Percentage);

  var roundedAllocations = for a in allocation
                           select new Allocation
                                  {
                                       Description = a.Description,
                                       Percentage = Math.Round(a.Percentage)
                                  };

I think this is what you're looking for. It could probably be cleaned up and optimized, but it takes the largest distance in rounding when deciding to round a number the other way.

    static List<double> Round2(List<double> actualAllocations)
    {
        List<double> actual = new List<double>();
        actual.AddRange(actualAllocations);

        List<double> rounded = new List<double>();
        foreach (var a in actual)
            rounded.Add(Math.Round(a));

        if (rounded.Sum() == 100)
        {
            return rounded;
        }
        else
        {
            bool roundUp = rounded.Sum() < 100;

            for (int i = 0; i < Math.Abs(100 - rounded.Sum()); i++)
            {
                var index = actual.IndexOf(
                    (from a in actual
                    orderby Math.Abs(Math.Round(a) - a) descending
                    select a).First());

                if (roundUp)
                    actual[index]++;
                else
                    actual[index]--;
            }
        }

        rounded.Clear();
        foreach (var a in actual)
            rounded.Add(Math.Round(a));

        return rounded;
    }