Assegnare una matrice di numeri interi che compensa in modo proporzionale gli errori di arrotondamento

Question

Ho una matrice di valori non negativi. Voglio costruire un array di valori con la somma di 20 in modo che siano proporzionali al primo array.

Questo sarebbe un problema facile, tranne che voglio che la matrice proporzionale somma esattamente a 20, compensando qualsiasi errore di arrotondamento.

Ad esempio, l'array

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

sarebbe cedere

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

Tuttavia, molti casi stanno per avere un sacco di errori di arrotondamento, come

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

cede ingenuamente

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

C'è un buon modo per ripartire l'array di output in modo che ne aggiunga fino a 20 ogni volta?

Answer 1

C'è una risposta molto semplice a questa domanda: ho fatto molte volte. Dopo ogni assegnazione nel nuovo array, si riducono i valori con cui si sta lavorando:

1. Chiamare il primo array A e il nuovo array proporzionale B (che inizia vuoto).
2. chiamata la somma di A elementi T
3. chiamata la somma desiderata S.
4. Per ogni elemento dell'array (i) effettuare le seguenti operazioni:
   a. B [i] = round (A [i]/T * S). (arrotondamento al numero intero più vicino, centesimo o altro)
   b. T = T - A [i]
   c. S = S - B [i]

Questo è tutto! Facile da implementare in qualsiasi linguaggio di programmazione o in un foglio di calcolo.

La soluzione è ottimale in quanto gli elementi della matrice risultante non saranno mai più di 1 lontano dai loro valori ideali, non arrotondati. Dimostriamo con il tuo esempio:
T = 36, S = 20. B [1] = round (A [1]/T * S) = 2. (idealmente, 1.666 ....)
T = 33, S = 18. B [2] = round (A [2]/T * S) = 2. (idealmente, 1.666 ....)
T = 30, S = 16. B [3] = round (A [3]/T * S) = 2. (idealmente, 1.666 ....)
T = 27, S = 14. B [4] = round (A [4]/T * S) = 2. (idealmente, 1.666 ....)
T = 24, S = 12. B [5] = round (A [5]/T * S) = 2. (idealmente, 1.666 ....)
T = 21, S = 10. B [6] = round (A [6]/T * S) = 1. (idealmente, 1.666 ....)
T = 18, S = 9.   B [7] = round (A [7]/T * S) = 9. (idealmente, 10)

Si noti che confrontando ogni valore in B con il suo valore ideale tra parentesi, la differenza non è mai superiore a 1.

È anche interessante notare che la riorganizzazione degli elementi nell'array può comportare diversi valori corrispondenti nell'array risultante. Ho trovato che organizzare gli elementi in ordine crescente è il migliore, perché si traduce nella media più piccola percentuale differenza tra reale e ideale.

Answer 2

Una soluzione banale che non esegue bene, ma fornirà il risultato giusto ...

Valuta un iteratore che, dato un array con otto interi (candidate) e la matrice input, uscita l'indice della elemento che è più lontana da essere proporzionale agli altri (pseudocodice):

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 

Poi basta fare questo

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

Se non esiste una soluzione ottimale, si orienterà verso l'inizio dell'array.

Utilizzando l'approccio di cui sopra, è possibile ridurre il numero di iterazioni arrotondando verso il basso (come avete fatto nel tuo esempio) e poi basta usare l'approccio di cui sopra per aggiungere ciò che è stato lasciato fuori a causa di errori di arrotondamento:

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

Answer 3

Hai impostato 3 requisiti incompatibili. Un array con valore intero proporzionale a [1,1,1] non può essere creato per sommare esattamente a 20. È necessario scegliere di interrompere uno dei requisiti "somma su esattamente 20", "proporzionale a input" e "valori interi".

Se si sceglie di interrompere il requisito per i valori interi, utilizzare il numero in virgola mobile o i numeri razionali. Se decidi di rompere il requisito di somma esatta, hai già risolto il problema. Scegliere di rompere la proporzionalità è un po 'più complicato. Un approccio che potreste fare è capire quanto lontano è la vostra somma, e quindi distribuire le correzioni casualmente attraverso l'array di output.Per esempio, se l'input è:

[1, 1, 1] 

allora si potrebbe prima renderlo riassumere così come possibile, pur essendo proporzionale:

[7, 7, 7] 

e dal 20 - (7+7+7) = -1, scegli un elemento per diminuire a caso:

[7, 6, 7] 

Se l'errore è stato 4, si potrebbe scegliere quattro elementi per incrementare.

Answer 4

Quindi le risposte e i commenti sopra sono stati utili ... in particolare il commento sommario decrescente di @Frederik.

La soluzione che ho trovato si avvantaggia del fatto che per un array di input v, sum (v_i * 20) è divisibile per sum (v). Quindi per ogni valore in v, moltiplicato per 20 e divido per la somma. Mantengo il quoziente e accumulo il resto. Ogni volta che l'accumulatore è maggiore della somma (v), ne aggiungo uno al valore. In questo modo sono garantito che tutti i rimanenti vengono inseriti nei risultati.

È leggibile? Ecco l'implementazione 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 

(ho aggiunto un miglioramento che, se l'accumulatore> resto, ho incrementare il valore precedente invece del valore corrente)

Answer 5

Il tuo problema è simile a un proportional representation dove si vuole per condividere i seggi N (nel tuo caso 20) tra i partiti proporzionalmente ai voti ottenuti, nel tuo caso [3, 3, 3, 3, 3, 18]

Ci sono diversi metodi usati in diversi paesi per gestire il problema di arrotondamento. My code sotto utilizza il metodo Hagenbach-Bischoff quota utilizzato in Svizzera, che assegna fondamentalmente i posti rimanenti dopo una divisione intera da (N + 1) a parti che hanno la più alta resto:

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's 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 

Tuttavia, questo metodo non sempre danno la stesso numero di seggi alle feste con perfetta uguaglianza come nel tuo caso:

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