Phân bổ một mảng các số nguyên tương ứng bù cho các lỗi làm tròn

Question

Tôi có một mảng các giá trị không âm. Tôi muốn xây dựng một mảng các giá trị tổng là 20 để chúng tỷ lệ thuận với mảng đầu tiên.

Đây sẽ là một vấn đề dễ dàng, ngoại trừ việc tôi muốn mảng tỷ lệ tổng hợp chính xác 20, bù cho bất kỳ lỗi làm tròn nào.

Ví dụ, mảng

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

sẽ mang lại

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

Tuy nhiên, hầu hết các trường hợp sẽ có rất nhiều sai sót làm tròn, giống như

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

ngây thơ mang

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

Có cách nào tốt để phân bổ mảng đầu ra sao cho nó thêm tối đa 20 lần không?

Answer 1

Có một câu trả lời rất đơn giản cho câu hỏi này: Tôi đã thực hiện nhiều lần. Sau mỗi lần gán vào mảng mới, bạn giảm các giá trị mà bạn đang làm việc như sau:

1. Gọi mảng đầu tiên A và mảng B tỷ lệ mới (bắt đầu trống).
2. Gọi tổng Một yếu tố T
3. Gọi tổng mong muốn S.
4. Đối với mỗi phần tử của mảng (i) làm như sau:
   a. B [i] = vòng (A [i]/T * S). (làm tròn đến số nguyên gần nhất, xu hoặc bất cứ thứ gì được yêu cầu)
   b. T = T - A [i]
   c. S = S - B [i]

Vậy đó! Dễ triển khai bằng bất kỳ ngôn ngữ lập trình nào hoặc trong bảng tính.

Giải pháp tối ưu ở chỗ các phần tử của mảng kết quả sẽ không bao giờ lớn hơn 1 so với các giá trị lý tưởng, không làm tròn của chúng. Hãy minh họa bằng ví dụ của bạn:
T = 36, S = 20. B [1] = vòng (A [1]/T * S) = 2. (lý tưởng, 1.666 ....)
T = 33, S = 18. B [2] = vòng (A [2]/T * S) = 2. (lý tưởng, 1.666 ....)
T = 30, S = 16. B [3] = vòng (A [3]/T * S) = 2. (lý tưởng, 1.666 ....)
T = 27, S = 14. B [4] = vòng (A [4]/T * S) = 2. (lý tưởng, 1.666 ....)
T = 24, S = 12. B [5] = vòng (A [5]/T * S) = 2. (lý tưởng, 1.666 ....)
T = 21, S = 10. B [6] = vòng (A [6]/T * S) = 1. (lý tưởng, 1.666 ....)
T = 18, S = 9.   B [7] = vòng (A [7]/T * S) = 9. (lý tưởng, 10)

Lưu ý rằng so sánh mọi giá trị trong B với giá trị lý tưởng trong dấu ngoặc đơn, sự chênh lệch không bao giờ lớn hơn 1.

Cũng cần lưu ý rằng sắp xếp lại các phần tử trong mảng có thể dẫn đến các giá trị tương ứng khác nhau trong mảng kết quả. Tôi đã tìm thấy rằng sắp xếp các yếu tố theo thứ tự tăng dần là tốt nhất, bởi vì nó kết quả ở mức trung bình nhỏ nhất là tỷ lệ phần trăm khác biệt giữa thực tế và lý tưởng.

Answer 2

Một giải pháp ngây thơ mà không hoạt động tốt, nhưng sẽ cung cấp kết quả đúng ...

Viết một iterator rằng đưa ra một mảng với tám số nguyên (candidate) và input mảng, đầu ra chỉ số của yếu tố đó là xa xa là tỷ lệ thuận với những người khác (giả):

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 

Sau đó chỉ cần làm điều này

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

Nếu không có giải pháp tối ưu, nó sẽ nghiêng về phía đầu của mảng.

Sử dụng phương pháp trên, bạn có thể giảm số lần lặp lại bằng cách làm tròn xuống (như bạn đã làm trong ví dụ của bạn) và sau đó chỉ cần sử dụng phương pháp trên để thêm những gì đã được bỏ qua do lỗi làm tròn:

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

Answer 3

Bạn đã đặt 3 yêu cầu không tương thích. Một mảng có giá trị số nguyên tỷ lệ với [1,1,1] không thể được thực hiện để tổng hợp thành chính xác 20. Bạn phải chọn ngắt một trong các yêu cầu "tổng giá trị chính xác 20", "tỷ lệ thuận với đầu vào" và "giá trị số nguyên".

Nếu bạn chọn phá vỡ yêu cầu cho giá trị số nguyên, hãy sử dụng dấu phẩy động hoặc số hợp lý. Nếu bạn chọn phá vỡ yêu cầu tổng chính xác, thì bạn đã giải quyết được vấn đề. Lựa chọn để phá vỡ tỷ lệ là một chút phức tạp hơn. Một cách tiếp cận bạn có thể thực hiện là tìm ra cách xa tổng của bạn, và sau đó phân phối các hiệu chỉnh ngẫu nhiên thông qua mảng đầu ra.Ví dụ, nếu đầu vào của bạn là:

[1, 1, 1] 

thì trước tiên bạn có thể làm cho nó tổng hợp cũng như có thể trong khi vẫn đang được theo tỷ lệ:

[7, 7, 7] 

và kể từ 20 - (7+7+7) = -1, chọn một yếu tố để giảm giá trị một cách ngẫu nhiên:

[7, 6, 7] 

Nếu lỗi là 4, bạn sẽ chọn bốn yếu tố để tăng.

Answer 4

Vì vậy, câu trả lời và nhận xét ở trên hữu ích ... đặc biệt là nhận xét tổng giảm từ @Frederik.

Giải pháp tôi đưa ra có lợi dụng thực tế là đối với mảng đầu vào v, tổng (v_i * 20) chia hết cho tổng (v). Vì vậy, đối với mỗi giá trị trong v, tôi mulitply 20 và chia cho tổng. Tôi giữ thương, và tích lũy phần còn lại. Bất cứ khi nào bộ tích lũy lớn hơn tổng (v), tôi thêm một giá trị vào giá trị. Bằng cách đó, tôi được đảm bảo rằng tất cả các phần còn lại được đưa vào kết quả.

Điều đó có dễ đọc không? Dưới đây là thực hiện bằng 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 

(tôi đã thêm một nâng cao rằng nếu accumulator> còn lại, tôi tăng giá trị trước đó thay vì giá trị hiện tại)

Answer 5

Vấn đề của bạn là tương tự như một proportional representation nơi bạn muốn để chia sẻ N ghế (trong trường hợp của bạn 20) giữa các bên tương ứng với số phiếu mà họ nhận được, trong trường hợp của bạn [3, 3, 3, 3, 3, 3, 18]

Có một số phương pháp được sử dụng ở các quốc gia khác nhau xử lý vấn đề làm tròn. My code dưới đây sử dụng phương pháp Hagenbach-Bischoff quota sử dụng ở Thụy Sĩ, mà về cơ bản phân bổ số ghế còn lại sau khi một bộ phận nguyên do (N + 1) để các bên có thời gian còn lại cao nhất:

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 

Tuy nhiên phương pháp này không phải lúc nào cung cấp cho các cùng số chỗ ngồi cho các bên có sự bình đẳng hoàn hảo như trong trường hợp của bạn:

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