Apportionment paradox Given:


A natural number S.
A list of N rational weights W that sum to 1.


Return a list L of N non-negative integers, such that:

(1) sum(L) = S
(2) sum((S⋅W_i - L_i)^2) is minimal


In other words, approximate S⋅W_is with integers as closely as possible.

Examples:

1 [0.4 0.3 0.3] = [1 0 0]
3 [0 1 0] = [0 3 0]
4 [0.3 0.4 0.3] = [1 2 1]
5 [0.3 0.4 0.3] = [2 2 1] or [1 2 2] but not [1 3 1]
21 [0.3 0.2 0.5] = [6 4 11]
5 [0.1 0.2 0.3 0.4] = [1 1 1 2] or [0 1 2 2]
4 [0.11 0.3 0.59] = [1 1 2]
10 [0.47 0.47 0.06] = [5 5 0]
10 [0.43 0.43 0.14] = [4 4 2]
11 [0.43 0.43 0.14] = [5 5 1]


Rules:


You can use any input format at all, or just provide a function that accepts the input as arguments.


Background:

This problem comes up when displaying S of different types of items in different proportions Wi with regard to the types.

Another example of this problem is proportional political representation, see the apportionment paradox. The last two test cases are known as Alabama paradox.


  As a statistician, I recognised this problem as equivalent to a
  problem encountered in identifying sample sizes when conducting a
  stratified sample. In that situation, we want to make the proportion
  of each stratum in the sample equal to the proportion of each stratum
  in the population.
  — @tomi
Python 2, 95 83 132 125 143

My first (and second) (and third) algorithm had problems so after a (another!) rewrite and more testing, here is (I really hope) a correct and fast solution:

def a(b,h):
 g=h;c=[];d=[]
 for w in b:f=int(w*h);d+=[f];c+=[h*w-f];g-=f
 if g:
  for e in sorted(c)[-g:]:i=c.index(e);c[i]=2;d[i]+=1
 return d


The source before the minifier now looks like:

# minified 143 bytes
def golfalloc(weights, num):
    # Tiny seq alloc for golfing
    gap = num;
    errors = [];
    counts = []
    for w in weights :
        count = int(w*num);
        counts += [count];
        errors += [num*w - count];
        gap -= count
    if gap:
        for e in sorted(errors)[-gap:] :
            i = errors.index(e);
            errors[i] = 2;
            counts[i] += 1
    return counts


The tests return:

Pass                    Shape    N               Result Error                        AbsErrSum
ok            [0.4, 0.3, 0.3]    1            [1, 0, 0] -0.60,+0.30,+0.30                 1.20
ok                  [0, 1, 0]    3            [0, 3, 0] +0.00,+0.00,+0.00                 0.00
ok            [0.3, 0.4, 0.3]    4            [1, 2, 1] +0.20,-0.40,+0.20                 0.80
ok            [0.3, 0.4, 0.3]    5            [2, 2, 1] -0.50,+0.00,+0.50                 1.00
ok            [0.3, 0.2, 0.5]   21           [6, 4, 11] +0.30,+0.20,-0.50                 1.00
ok       [0.1, 0.2, 0.3, 0.4]    5         [1, 1, 1, 2] -0.50,+0.00,+0.50,+0.00           1.00
ok          [0.11, 0.3, 0.59]    4            [1, 1, 2] -0.56,+0.20,+0.36                 1.12
ok         [0.47, 0.47, 0.06]   10            [5, 5, 0] -0.30,-0.30,+0.60                 1.20
ok         [0.43, 0.43, 0.14]   10            [4, 4, 2] +0.30,+0.30,-0.60                 1.20
ok         [0.43, 0.43, 0.14]   11            [5, 5, 1] -0.27,-0.27,+0.54                 1.08


This algorithm is similar to other answers here. It is O(1) for num so it has the same run time for integers 10 and 1000000. It is theoretically O(nlogn) for the number of weights (because of the sort). If this withstands all other tricky input cases, it will replace the algorithm below in my programming toolbox.

Please don't use that algorithm with anything not golfy. I made compromises in speed to minimise source size. The following code uses the same logic but is much faster and more useful:

def seqalloc(anyweights, num):
    # Distribute integer num depending on weights.
    # weights may be non-negative integers, longs, or floats.
    totalbias = float(sum(anyweights))
    weights = [bias/totalbias for bias in anyweights]
    counts = [int(w*num) for w in weights]
    gap = num - sum(counts)
    if gap:
        errors = [num*w - q for w,q in zip(weights, counts)]
        ordered = sorted(range(len(errors)), key=errors.__getitem__)
        for i in ordered[-gap:]:
            counts[i] += 1
    return counts


The value of num doesn't affect speed significantly. I have tested it with values from 1 to 10^19. The execution time varies linearly with the number of weights. On my computer it takes 0.15 seconds with 10^5 weights and 15 seconds with 10^7 weights. Note that the weights are not restricted to fractions that sum to one. The sort technique used here is also about twice as fast as the traditional sorted((v,i) for i,v in enumerate...) style.

Original Algorithm

This was a function in my toolbox, modified a little for golf. It was originally from a SO answer. And it is wrong.

def seqalloc(seq, num):
    outseq = []
    totalw = float(sum(seq))
    for weight in seq:
        share = int(round(num * weight / totalw)) if weight else 0
        outseq.append(share)
        totalw -= weight
        num -= share
    return outseq


It gives an approximation, but is not always correct, although the sum(outseq) == num is maintained. Fast but not recommended.

Thanks to @alephalpha and @user23013 for spotting the errors.

EDIT: Set totalw (d) to be 1 as OP specifies the sum of weights will always be 1. Now 83 bytes.

EDIT2: Fixed bug found for [0.4, 0.3, 0.3], 1.

EDIT3: Abandoned flawed algorithm. Added better one.

EDIT4: This is getting ridiculous. Replaced with correct (I really hope so) algorithm.

EDIT5: Added not-golfy code for others that may like to use this algorithm.