Javascript implementation of the largest remainder method http://en.wikipedia.org/wiki/Largest_remainder_method

example.coffee

values = [
    13.626332
    47.989636
    9.596008
    28.788024
]

# Round these percentage values into integers, ensuring that they equal 100% at the end.
roundedValues = getLargestRemainder values, 100
# [14, 48, 9, 29]

lr.coffee

# Uses underscore.js, for brevity.

getLargestRemainder = (values, desiredSum) ->
    sum = 0
    parts = _.map values, (item, i) ->
        # Get rounded down integer values.
        int = item | 0
        sum += int
        return {
            integer: int
            decimal: item % 1
            # Used to return values in original order.
            originalIndex: i
        }

    if sum isnt desiredSum
        # Sort in descending order.
        parts = _(parts).sortBy('decimal').reverse()

        diff = desiredSum - sum
        i = 0
        # Distribute additions.
        while i < diff
            parts[i].integer++
            i++

    return _.pluck _(parts).sortBy('originalIndex'), 'integer'
    

Hey @hijonathan! I found this gist very useful and am thinking of open-sourcing something where I was heavily influenced by it. Would you be okay with this? Feel free to shoot me an e-mail (it's on my GitHub profile).

Hey @hijonathan, thanks for this gist!

I translated it to typescript. Will leave the code here just in case anyone needs it.

private getLargestRemainder(values: number[], desiredSum: number) {
   let sum = 0;
   let valueParts = values.map((value: number, index: number) => {
     // Get rounded down integer values.
     let integerValue = value | 0;
     sum += integerValue;
     return {
         integer: integerValue, // Integer part of the value
         decimal: value % 1, // Decimal part of the value
         originalIndex: index  // Used to return values in original order.
     }
   })

   if (sum != desiredSum) {
     // Sort values by decimal part
     valueParts = valueParts.sort(x => x.decimal);

     const diff = desiredSum - sum;
     let i = 0;

     // Distribute the difference.
     while (i < diff) {
       valueParts[i].integer++;
       i++;
     }
   }
   
   return valueParts.sort(x => x.originalIndex).map(p => p.integer);
 }

Hey @djabif, I don't get much of coffee and your implementation really helped. Thanks!!

I just changed:

     valueParts = valueParts.sort(x => x.decimal);
     valueParts.sort(x => x.originalIndex)

to, respectively,

     valueParts = valueParts.sort((a, b) => b.decimal - a.decimal);
     valueParts.sort((a, b) => a.originalIndex - b.originalIndex)

as that is required to correctly sort the list by descending/ascending. Otherwise JS will just sort them alphabetically which can lead to errors.

Hey @djabif, I don't get much of coffee and your implementation really helped. Thanks!!

I just changed:

     valueParts = valueParts.sort(x => x.decimal);
     valueParts.sort(x => x.originalIndex)

to, respectively,

     valueParts = valueParts.sort((a, b) => b.decimal - a.decimal);
     valueParts.sort((a, b) => a.originalIndex - b.originalIndex)

as that is required to correctly sort the list by descending/ascending. Otherwise JS will just sort them alphabetically which can lead to errors.

Thanks for your fix and for the gist @hijonathan.

FYI the values are different on Chrom/Firefox than in Safari without this fix.