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

• Could you say in words what the task is? I'm having trouble decompressing the expressions into something intuitive.
– xnor
Feb 14, 2015 at 19:13
• Both should be ≤, fixed. The task is to present an integer as a sum of integers based on weights. The remainder should distribute favoring the highest weights, though I am not sure this requirement is encoded correctly? This is interesting because round(A + B) != round(A) + round(B), a short solution requires an insight on what's going on here. Feb 14, 2015 at 19:40
• Maybe change the rules to minimize the sum of the distances L[i] - S*W[i] squared, instead of rule 2 and rule 3. This would approximate S*W[i]. Feb 14, 2015 at 20:00
• Also [0 1 2 2]  is another possible solution for 5 [0.1 0.2 0.3 0.4] Feb 14, 2015 at 20:44
• Maybe you should add an example for 1 [0.4 0.3 0.3] Feb 15, 2015 at 13:07

# Python 2, 9583132125 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.

• a([0.4, 0.3, 0.3], 1) returns [0, 1, 0], while the correct answer is [1, 0, 0]. Feb 15, 2015 at 11:08
• Still wrong. a([0.11,0.3,0.59],4) returned [0, 1, 3]. Should be [1, 1, 2]. Feb 16, 2015 at 22:39
• f([0.47,0.47,0.06],10) returned [5, 4, 1]. Should be [5, 5, 0]. Feb 17, 2015 at 11:19
• I think it's correct now. Feb 17, 2015 at 18:20
• @CarpetPython I went through a similar process with this algorithm, and this is how I came up with this problem. If they take away your license, they should take mine too :) Feb 20, 2015 at 12:32

# APL, 21

{{⍵+1=⍋⍋⍵-⍺}⍣⍺/⍺0×⊂⍵}


This is a translation from aditsu's 37 byte CJam answer.

### Explanation

 {      ⍵-⍺}            ⍝ Right argument - left argument.
{  1=⍋⍋⍵-⍺}            ⍝ Make one of the smallest number 1, others 0.
{⍵+1=⍋⍋⍵-⍺}            ⍝ Add the result and the right argument together.
{⍵+1=⍋⍋⍵-⍺}⍣⍺          ⍝ Repeat that S times. The result of each iteration is the new right argument.
⊂⍵    ⍝ Return enclosed W, which is taken as one unit in APL.
⍺0×⊂⍵    ⍝ Return S*W and 0*W.
{{⍵+1=⍋⍋⍵-⍺}⍣⍺/⍺0×⊂⍵}   ⍝ Make S*W the left argument, 0*W the right argument in the first iteration.


# Mathematica, 675046 45 chars

f=(b=⌊1##⌋;b[[#~Ordering~-Tr@#&[b-##]]]++;b)&


Ungolfed:

f[s_, w_] := Module[{a = s*w, b, c, d},
b = Floor[a];
c = b - a;
d = Ordering[c, -Total[c]];
b[[d]] += 1;
b]


Example:

f[5,{0.1,0.2,0.3,0.4}]


{1, 1, 1, 2}

• My goodness, that's short, considering it's Mathematica! Feb 15, 2015 at 15:15

# CJam - 37

q~:W,0a*\:S{[_SWf*]z::-_:e<#_2$=)t}*p  Try it online Explanation: q~ read and evaluate the input (pushing the number and the array on the stack) :W, save the array in variable W and calculate its length (N) 0a* make an array of N zeros (the initial "L") \:S swap it with the number and save the number in S {…}* execute the block S times [_SWf*] make a matrix with 2 rows: "L" and S*W z transpose the matrix, obtaining rows of [L_i S*W_i] ::-_ convert to array of L_i-S*W_i and duplicate :e< get the smallest element # find its index in the unsorted array, i.e. the "i" with the largest S*W_i-L_i _2$=)t     increment L_i
p              print the result nicely


Notes:

• The complexity is about O(S*N), so it gets really slow for large S
• CJam is sorely lacking arithmetic operators for 2 arrays, something I plan to implement later

Different idea - 46

q~:Sf*_:m[_:+S\-@[1f%_,,]z{0=W*}$<{1=_2$=)t}/p


Try it online

This is much more straightforward and efficient, but alas, quite a bit longer. The idea here is to start with L_i=floor(S*W_i), determine the difference (say D) between S and their sum, find the D indices with the largest fractional part of S*W_i (by sorting and taking top D) and increment L_i for those indices. Complexity O(N*log(N)).

• Now there is the O(N) :e<. Feb 14, 2015 at 23:42
• @user23013 oh yeah, for the first program, thanks Feb 14, 2015 at 23:44
• That was quick! Congrats 🌟 Feb 14, 2015 at 23:47
• For those wondering, replacing the sort with a linear time selection algorithm would yield O(n) instead of the actual O(nlogn) caused by the sort: Find the D-th largest element, P, in O(N), then increment elements that are ≥P D times (O(N) since D <= N). Feb 17, 2015 at 1:59
• @glebm that's pretty cool, but I think there is a problem if multiple elements have the same value (P). Maybe you can solve it in 2 passes then: first increment and count the elements >P, then you know how many elements =P are needed. Or if you can get that information from the selection algorithm, even better. Feb 17, 2015 at 14:56

# JavaScript (ES6) 126 130 104 115 156 162 194

After all the comments and test cases in @CarpetPython's answer, back to my first algorithm. Alas, the smart solution does not work. Implementation shortened a little, it still tries all the possible solutions, calc the squared distance and keep the minimum.

Edit For each output element of weight w, 'all' the possible values are just 2: trunc(w*s) and trunc(w*s)+1, so there are just (2**elemensts) possible solutions to try.

Q=(s,w)=>
(n=>{
for(i=0;
r=q=s,(y=i++)<1<<w.length;
q|r>n||(n=r,o=t))
t=w.map(w=>(f=w*s,q-=d=0|f+(y&1),y/=2,f-=d,r+=f*f,d));
})()||o


Test In Firefox/FireBug console

;[[ 1,  [0.4, 0.3, 0.3]      ]
, [ 3,  [0, 1, 0]            ]
, [ 4,  [0.3, 0.4, 0.3]      ]
, [ 5,  [0.3, 0.4, 0.3]      ]
, [ 21, [0.3, 0.2, 0.5]      ]
, [ 5,  [0.1, 0.2, 0.3, 0.4] ]
, [ 4,  [0.11, 0.3, 0.59]    ]
, [ 10, [0.47, 0.47, 0.06]   ]
, [ 10, [0.43, 0.43, 0.14]   ]
, [ 11, [0.43, 0.43, 0.14]   ]]
.forEach(v=>console.log(v[0],v[1],Q(v[0],v[1])))


Output

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] [1, 2, 2]
21 [0.3, 0.2, 0.5] [6, 4, 11]
5 [0.1, 0.2, 0.3, 0.4] [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]


That's a smarter solution. Single pass on weigth array.
For each pass i find the current max value in w. I change this value in place with the weighted integer value (rounded up), so if s==21 and w=0.4, we got 0.5*21 -> 10.5 -> 11. I store this value negated, so it can't be found as max in the next loop. Then I reduce the total sum accordingly (s = s-11) and also reduce the total of the weigths in variable f.
The loop ends when ther is no max above 0 to be found (all the values != 0 have been managed).
At last I returns the values changed to positive again. Warning this code modifies the weights array in place, so it must be called with a copy of original array

F=(s,w)=>
(f=>{
for(;j=w.indexOf(z=Math.max(...w)),z>0;f-=z)
s+=w[j]=-Math.ceil(z*s/f);
})(1)||w.map(x=>0-x)


My first try

Not so a smart solution. For every possible result, it evaluates the difference, and keeps the minimum.

F=(s,w,t=w.map(_=>0),n=NaN)=>
(p=>{
for(;p<w.length;)
++t[p]>s?t[p++]=0
:t.map(b=>r+=b,r=p=0)&&r-s||
t.map((b,i)=>r+=(z=s*w[i]-b)*z)&&r>n||(n=r,o=[...t])
})(0)||o


Ungolfed And explained

F=(s, w) =>
{
var t=w.map(_ => 0), // 0 filled array, same size as w
n=NaN, // initial minumum NaN, as "NaN > value"  is false for any value
p, r
// For loop enumerating from [1,0,0,...0] to [s,s,s...s]
for(p=0; p<w.length;)
{
++t[p]; // increment current cell
if (t[p] > s)
{
// overflow, restart at 0 and point to next cell
t[p] = 0;
++p;
}
else
{
// increment ok, current cell is the firts one
p = 0;
r = 0;
t.map(b => r += b) // evaluate the cells sum (must be s)
if (r==s)
{
// if sum of cells is s
// evaluate the total squared distance (always offset by s, that does not matter)
t.map((b,i) => r += (z=s*w[i]-b)*z)
if (!(r > n))
{
// if less than current mininum, keep this result
n=r
o=[...t] // copy of t goes in o
}
}
}
}
return o
}


# CJam, 48 bytes

A straight forward solution to the problem.

q~:Sf*:L,S),a*{m*{(+}%}*{1bS=},{L]z::-Yf#:+}$0=p  Input goes like [0.3 0.4 0.3] 4  Explanation: q~:S "Read and parse the input, store sum in S"; f*:L "Do S.W, store the dot product in L"; S), "Get array of 0 to S"; , a* "Create an array with N copies of the above array"; {m*{(+}%}* "Get all possible N length combinations of 0 to S ints"; {1bS=}, "Filter to get only those which sum up to S"; {L]z::-Yf#:+}$                       "Sort them based on (S.W_i - L_i)^2 value";
L                                   "Put the dot product after the sum combination";
]z                                 "Wrap in an array and transpose";
::-                              "For each row, get difference, i.e. S.W_i - L_i";
Yf#                           "Square every element";
:+                         "Take sum";
0=p                    "After sorting on sum((S.W_i - L_i)^2), take the";
"first element, i.e. smallest sum and print it";


Try it online here

# Pyth: 40 bytes

Mhosm^-*Ghded2C,HNfqsTGmms+*G@Hb}bklHyUH


This defines a function g with 2 parameters. You can call it like Mhosm^-*Ghded2C,HNfqsTGmms+*G@Hb}bklHyUHg5 [0.1 0.2 0.3 0.4.

Try it online: Pyth Compiler/Executor

## Explanation:

mms+*G@Hb}bklHyUH     (G is S, H is the list of weights)
m             yUH    map each subset k of [0, 1, ..., len(H)-1] to:
m          lH          map each element b of [0, 1, ..., len(H)-1] to:
*G@Hb                  G*H[b]
+     }bk               + b in k
s                       floor(_)


This creates all possible solutions L, where L[i] = floor(S*W[i]) or L[i] = floor(S*W[i]+1). For instance, the input 4 [0.3 0.4 0.3 creates [[1, 1, 1], [2, 1, 1], [1, 2, 1], [1, 1, 2], [2, 2, 1], [2, 1, 2], [1, 2, 2], [2, 2, 2]].

fqsTG...
f    ... only use the solutions, where
qsTG       sum(solution) == G


Only [[2, 1, 1], [1, 2, 1], [1, 1, 2]] remain.

Mhosm^-*Ghded2C,HN
o                  order the solutions by
s                   the sum of
m         C,HN       map each element d of zip(H, solution) to
^-*Ghded2           (G*d[0] - d[1])^2
h                   use the first element (minimum)
M                    define a function g(G,H): return _


# Mathematica 108

s_~f~w_:=Sort[{Tr[(s*w-#)^2],#}&/@
Flatten[Permutations/@IntegerPartitions[s,{Length@w},0~Range~s],1]][[1,2]]


f[3, {0, 1, 0}]
f[4, {0.3, 0.4, 0.3}]
f[5, {0.3, 0.4, 0.3}]
f[21, {0.3, 0.2, 0.5}]
f[5, {0.1, 0.2, 0.3, 0.4}]


{0, 3, 0}
{1, 2, 1}
{1, 2, 2}
{6, 4, 11}
{0, 1, 2, 2}

## Explanation

Ungolfed

f[s_,w_]:=
Module[{partitions},
partitions=Flatten[Permutations/@IntegerPartitions[s,{Length[w]},Range[0,s]],1];
Sort[{Tr[(s *w-#)^2],#}&/@partitions][[1,2]]]


IntegerPartitions[s,{Length@w},0~Range~s] returns all the integer partitions of s, using elements taken from the set {0, 1, 2, ...s} with the constraint that the output should contain the same number of elements as in the set of weights, w.

Permutations gives all of the ordered arrangements of each integer partition.

{Tr[(s *w-#)^2],#} returns a list of ordered pairs, {error, permutation} for each permutation.

Sort[...] sorts the list of {{error1, permutation1},{error2, permutation2}...according to the size of the error.

[[1,2]]] or Part[<list>,{1,2}] returns the second item of the first element in the sorted list of {{error, permutation}...}. In other words, it returns the permutation with the smallest error.

# R, 8580 76

Uses the Hare Quota method.

Removed a couple after seeing the spec that W will sum to 1

function(a,b){s=floor(d<-b*a);s[o]=s[o<-rev(order(d%%1))[0:(a-sum(s))]]+1;s}


Test run

> (function(a,b){s=floor(d<-b/(sum(b)/a));s[o]=s[o<-rev(order(d%%1))[0:(a-sum(s))]]+1;s})(3,c(0,1,0))
[1] 0 3 0
> (function(a,b){s=floor(d<-b/(sum(b)/a));s[o]=s[o<-rev(order(d%%1))[0:(a-sum(s))]]+1;s})(1,c(0.4,0.3,0.3))
[1] 1 0 0
> (function(a,b){s=floor(d<-b/(sum(b)/a));s[o]=s[o<-rev(order(d%%1))[0:(a-sum(s))]]+1;s})(4,c(0.3, 0.4, 0.3))
[1] 1 2 1
> (function(a,b){s=floor(d<-b/(sum(b)/a));s[o]=s[o<-rev(order(d%%1))[0:(a-sum(s))]]+1;s})(5,c(0.3, 0.4, 0.3))
[1] 1 2 2
> (function(a,b){s=floor(d<-b/(sum(b)/a));s[o]=s[o<-rev(order(d%%1))[0:(a-sum(s))]]+1;s})(21,c(0.3, 0.2, 0.5))
[1]  6  4 11
> (function(a,b){s=floor(d<-b/(sum(b)/a));s[o]=s[o<-rev(order(d%%1))[0:(a-sum(s))]]+1;s})(5,c(0.1,0.2,0.3,0.4))
[1] 1 1 1 2
>


# Python, 139128 117 bytes

def f(S,W):
L=(S+1,0,[]),
for n in W:L=[(x-i,y+(S*n-i)**2,z+[i])for x,y,z in L for i in range(x)]
return min(L)[2]


## Previous itertools solution, 139 bytes

from itertools import*
f=lambda S,W:min((sum(x)!=S,sum((S*a-b)**2for a,b in zip(W,x)),list(x))for x in product(*tee(range(S+1),len(W))))[2]

• I was wondering if an itertools solution would be possible. Nice work +1. Am I right in thinking this has O(n^4) time complexity? Feb 17, 2015 at 4:06
• Itertools solution was O(S^len(W)) actually :P. New solution's a lot faster, but still slow Feb 17, 2015 at 4:55

# Octave, 87 76

Golfed:

function r=w(s,w)r=0*w;for(i=1:s)[m,x]=max(s*w-r);r(x)+=1;endfor endfunction


Ungolfed:

function r=w(s,w)
r=0*w;   # will be the output
for(i=1:s)
[m,x]=max(s*w-r);
r(x)+=1;
endfor
endfunction


(Blasted "endfor" and "endfunction"! I'll never win but I do enjoy golfing with a "real" language.)

• Nice algorithm. You can replace zeros(size(w)) with 0*w. Feb 18, 2015 at 6:33
• Nice! Why didn't I think of that? Feb 18, 2015 at 14:14

# T-SQL, 167 265

Because I like to try and do these challenges in a query as well.

Turned it into an inline function to better fit the spec and created a type for the table data. It cost a bit, but this was never going to be a contender. Each statement needs to be run separately.

CREATE TYPE T AS TABLE(A INT IDENTITY, W NUMERIC(9,8))
CREATE FUNCTION W(@ int,@T T READONLY)RETURNS TABLE RETURN SELECT CASE WHEN i<=@-SUM(g)OVER(ORDER BY(SELECT\))THEN g+1 ELSE g END R,A FROM(SELECT A,ROW_NUMBER()OVER(ORDER BY (W*@)%1 DESC)i,FLOOR(W*@)g FROM @T)a


In use

DECLARE @ INT = 21
DECLARE @T T
INSERT INTO @T(W)VALUES(0.3),(0.2),(0.5)
SELECT R FROM dbo.W(@,@T) ORDER BY A

R
---------------------------------------
6
4
11