Is there a better algorithm to distribute values from one source to X destinations minimizing their difference?
I have some source integer. I need to know
how much of that value I need to distribute among some other values the proportion of that source to be distributed among other ordered integers in order to align make them equal as much as possible.
source = 20
destinations = [10, 20, 30, 40]
result should = [15, 5]
this will make final destinations look like [25, 25, 30, 40]
Here the source "20" was divided among first 2 destinations in attempt to compensate their difference as much as possible. So the result is the list of integers: [15, 5].
Each destination has some common limit but it never overflows. If source value exceeds sum of destinations' "free room", than I just fill destinations up to it: sharing isn't needed. But if source is smaller then some sharing logic is needed.
# Other test cases (each destination's capacity is limited with 100): # nothing to share: share(0, [10, 20, 30, 40]) ==  # finally keeps dests the same: [10, 20, 30, 40] # source exceeds total destinations' capacity (999 > 90+80+70+60==300) # no special algo is required: share(999, [10, 20, 30, 40]) == [90, 80, 70, 60] # finally top-fills dests: [100, 100, 100, 100] # source is smaller than first 2 items diffs (5 < 20-10=10) share(5, [10, 20, 30, 40]) ==  # finally fills just the most poor dest: [15, 20, 30, 40] # source is larger than first 2 items diffs (15 > 20-10=10) # 1 indivisible point is left unshareable share(15, [10, 20, 30, 40]) == [12, 2] # finally fills 2 most poor dests also equalizing them: [22, 22, 30, 40] # and so on...
I can't figure out better naming and description of that problem.
Here is the code in python that I managed to implement. But I feel the possibility of some better idea though:
def share(available, members): avail = available imembers = iter(members) member_ = next(imembers) i = 1 distr =  for member in imembers: avail -= (member.value - member_.value) * i if avail < 0: distr = list(member_.value - imember.value for imember in members[0:i]) equal_share = int((source.value - sum(sharing)) / i) distr = list(share + equal_share for share in distr[0:i]) break member_ = member i += 1 return distr
The final solution / with help of @Euphoric
def diff(values, target): # return the difference list of values and target return [target - v for v in values] def distribute(available, members, strict_equal=False): # find across how many 'members' we must distribute 'available' # and discover the total sum of those values # in order to get diff list for them and the target value total = available idx = None for idx, member in enumerate(members): total += member if idx >= len(members)-1 \ or total // (idx+1) <= members[idx+1]: break count = idx+1 dist = diff(members[0:count], total // count) if not strict_equal: for r in range(total % count): dist[r] += 1 return dist