Geek asks and answers

Select an array of integers proportionally compensating for rounding errors

I have an array of non-negative values. I want to build an array of values ​​whose sum is 20, so that they are proportional to the first array.

This would be an easy problem, except that I want the proportional array to sum exactly 20, compensating for any rounding error.

For example, an array

input = [400, 400, 0, 0, 100, 50, 50]

will give

output = [8, 8, 0, 0, 2, 1, 1]
sum(output) = 20

However, in most cases there will be many rounding errors, for example

input = [3, 3, 3, 3, 3, 3, 18]

naively gives

output = [1, 1, 1, 1, 1, 1, 10]
sum(output) = 16  (ouch)

Is there a good way to distribute the output array so that it adds up to 20 each time?

+5
source share
5 answers

: . , :

  • A B ( ).
  • A T
  • S.
  • (i) :
    . B [i] = round (A [i]/T * S). ( , )
    . T = T - A [i]
    . S = S - B [i]

! .

, 1 , . : T = 36, S = 20. B [1] = round (A [1]/T * S) = 2. ( 1.666....)
T = 33, S = 18. B [2] = round (A [2]/T * S) = 2. ( 1.666....) T = 30, S = 16. B [3] = round (A [3]/T * S) = 2. ( 1.666....) T = 27, S = 14. B [4] = round (A [4]/T * S) = 2. ( 1.666....)
T = 24, S = 12. B [5] = round (A [5]/T * S) = 2. ( 1.666....)
T = 21, S = 10. B [6] = round (A [6]/T * S) = 1. ( 1.666....) T = 18, S = 9 B [7] = round (A [7]/T * S) = 9. ( , 10)

, B , 1.
, . , , percent .

+4

, N ( 20) , , [3, 3, 3, 3, 3, 3, 18]

, . Hagenbach-Bischoff quota, , , (N + 1), , :

def proportional(nseats,votes):
    """assign n seats proportionaly to votes using Hagenbach-Bischoff quota
    :param nseats: int number of seats to assign
    :param votes: iterable of int or float weighting each party
    :result: list of ints seats allocated to each party
    """
    quota=sum(votes)/(1.+nseats) #force float
    frac=[vote/quota for vote in votes]
    res=[int(f) for f in frac]
    n=nseats-sum(res) #number of seats remaining to allocate
    if n==0: return res #done
    if n<0: return [min(x,nseats) for x in res] # see siamii comment
    #give the remaining seats to the n parties with the largest remainder
    remainders=[ai-bi for ai,bi in zip(frac,res)]
    limit=sorted(remainders,reverse=True)[n-1]
    #n parties with remainter larger than limit get an extra seat
    for i,r in enumerate(remainders):
        if r>=limit:
            res[i]+=1
            n-=1 # attempt to handle perfect equality
            if n==0: return res #done
    raise #should never happen

, :

proportional(20,[3, 3, 3, 3, 3, 3, 18])
[2,2,2,2,1,1,10]
+10

3 . Integer , [1,1,1], 20. " 20", " " " ".

, . , . . , , , , , . , :

[1, 1, 1]

, , :

[7, 7, 7]

20 - (7+7+7) = -1, :

[7, 6, 7]

4, .

+2

, , ...

, (candidate) input, , ():

function next_index(candidate, input)
    // Calculate weights
    for i in 1 .. 8
        w[i] = candidate[i] / input[i]
    end for
    // find the smallest weight
    min = 0
    min_index = 0
    for i in 1 .. 8
        if w[i] < min then
            min = w[i]
            min_index = i
        end if
    end for

    return min_index
 end function


result = [0, 0, 0, 0, 0, 0, 0, 0]
result[next_index(result, input)]++ for 1 .. 20

, .

, ( ), , , - :

result = <<approach using rounding down>>
while sum(result) < 20
    result[next_index(result, input)]++
+1

, ... @Frederik.

The solution I came up with uses the fact that for the input array v, the sum (v_i * 20) is divided by the sum (v). Thus, for each value in v, I mulitply by 20 and divide by the sum. I save the factor and accumulate the remainder. Whenever the battery is greater than the sum (v), I add it to the value. Thus, I am guaranteed that all the rest will roll into the results.

Is it picky? Here's the implementation in Python:

def proportion(values, total):
    # set up by getting the sum of the values and starting
    # with an empty result list and accumulator
    sum_values = sum(values)
    new_values = []
    acc = 0

    for v in values:
        # for each value, find quotient and remainder
        q, r = divmod(v * total, sum_values)

        if acc + r < sum_values:
            # if the accumlator plus remainder is too small, just add and move on
            acc += r
        else:
            # we've accumulated enough to go over sum(values), so add 1 to result
            if acc > r:
                # add to previous
                new_values[-1] += 1
            else:
                # add to current
                q += 1
            acc -= sum_values - r

        # save the new value
        new_values.append(q)

    # accumulator is guaranteed to be zero at the end
    print new_values, sum_values, acc

    return new_values

(I added an improvement, which, if the sum of the battery> balance, I increase the previous value instead of the current value)

0
source

More articles:


All Articles