CODEWITHSUNDEEP
c#math
Adam
Adam

Reputation: 2143

Rounding an arrays of values to 100%

I have an dictionary of lists of objects as shown below:

IDictionary<string, IList> MyItemDictionary

I work out the percentages by doing a for each through the dictionary with the code below:

IList<double> percentages = new List<double>();    

foreach(KeyValuePair<string, IList> pair in MyItemDictionary)
{
    double percentage = (100d/totalItemsCount)*pair.Value.Count;
    percentages.Add(percentage);
}

Basically I need to process the percentages list and round each percentage to a whole number BUT have them add up to 100. Accuracy is not of the highest importance but a sub 1 percentage i.e. 0.45 needs to be rounded to 1.

Does anyone know how to do this?

Upvotes: 2

Views: 2266

Answers (4)

Cogitator
Cogitator

Reputation: 154

This is my C# implementation of the Largest Remainder Method. I have not tested it extensively, but so far so good. There may be some edge cases where it doesn't work.

Here is a sample call:

var unrounded = new List { 1.0M, 1.5M, 1.5M, 1.5M, 1.5M, 1.5M, 1.5M, 1.5M, 1.5M, 1.5M, 1.5M, 1.5M, 1.5M, 1.5M, 1.5M, 1.5M, 1.5M, 1.5M, 1.5M, 1.5M, 1.5M, 1.5M, 1.5M, 1.5M, 1.5M, 1.5M, 1.5M, 1.5M, 1.5M, 1.5M, 1.5M, 1.5M, 1.5M, 1.5M, 1.5M, 1.5M, 1.5M, 1.5M, 1.5M, 1.5M, 1.5M, 1.5M, 1.5M, 1.5M, 1.5M, 1.5M, 1.5M, 1.5M, 1.5M, 1.5M, 1.5M, 1.5M, 1.5M, 1.5M, 1.5M, 1.5M, 1.5M, 1.5M, 1.5M, 1.5M, 1.5M, 1.5M, 1.5M, 1.5M, 1.5M, 1.5M, 1.5M };

var rounded = RoundNumberList(unrounded);

    /// <summary>
    /// Round list of numbers using the Largest Remainder Method. Sum of Numbers should equal 100.
    /// </summary>
    /// <param name="Numbers">List of decimals numbers to round</param>
    /// <returns>Rounded list of integers</returns>
    public static List<int> RoundNumberList(List<decimal> Numbers)
    {
        int sum = 0;
        var rounded = new Dictionary<int, decimal>();

        for (int i = 0; i < Numbers.Count; i++)
        {
            rounded.Add(i, Numbers[i]);
            sum += (int)Numbers[i];
        }

        if (sum > 100)
            throw new Exception("The sum of all numbers is > 100.");

        if (100 - sum > Numbers.Count)
            throw new Exception("The sum of all numbers is too low for rounding: " + sum.ToString());

        if (sum < 100)
        {
            // Sort descending by the decimal portion of the number
            rounded = rounded.OrderByDescending(n => n.Value-(int)n.Value).ToDictionary(x => x.Key, x => x.Value);

            int i = 0;  
            int diff = 100 - sum;

            foreach (var key in rounded.Keys.ToList())
            {
                rounded[key]++;
                i++;
                if (i >= diff) break;
            }

            // Put back in original order and return just integer portion
            return rounded.OrderBy(n => n.Key).Select(n => (int)n.Value).ToList();
        }
        else
        {
            // Return just integer portion
            return rounded.Select(n => (int)n.Value).ToList();
        }
    }

Upvotes: 3

starblue
starblue

Reputation: 56772

Take a look at how seats in a parliament are assigned based on votes for proportional representation. I would suggest the largest remainder method, because it uses time proportional to the number of items in your list.

Upvotes: 1

Martin Wickman
Martin Wickman

Reputation: 19905

If your percentage list ends up containing 1.5 + 1.5 + .. + 1.5 = 100.0 and you were to round them into 2 + 2 + .. + 2, you would end up with 134 as the total sum (~67 entries), not 100. The way to fix this, is to distribute the error (134-100=34) among the existing percentages. In this case, you would subtract 1 from 34 of the percentages so you end up with a series of 1 + 2 + 1 + 2 + .. + 2 = 100.0.

To find what "every other" means you simply do int(numberOfPercentages / theError) and that should give you the interval.

Also, you must take care not to subtract anything from your sub 1 percentages.

Oh, and in case all your percentages are sub 1, the problem cannot be solved :-(

Upvotes: 3

Paul Williams
Paul Williams

Reputation: 17020

Can you have an "Other" or "Misc" category? If you have many small percentages, and you round them all up or down, you will accumulate a huge error as wic pointed out. You might need a minmimum threshold beyond which you lump everything together as miscellaneous stuff.

Otherwise, I second wic's idea about summing up the percentages to find the error and then distributing the error over the largest percentages.

Upvotes: 1

Related Questions