Let's assume I have a bucket of identical items (n in number) distributed in identical buckets (m in number). The given distribution may or may not be fair/uniform. The goal is to write an algorithm that can uniformly redistribute these items by transferring some items. Each transfer has a cost associated with it, so the number of transfers must be minimum.
For example I have total 7 items in 3 buckets with this distribution. Input is a vector of size 'm' of number of items in each bucket with - 4, 2, 1
The solution would involve 1 transfer from bucket 1 to bucket 3 and the resulting distribution will look like - 3, 2, 2
Since n(7) is not perfectly divisible by m(3), this is the closest achievable uniform distribution.
Another sample case - input: {1, 4, 5, 11}
output: {5, 5, 5, 6}
Number of transfer to get to the output: 5
I'm looking for some existing algorithms that can solve this problem statement. Thanks!
While your use case doesn't necessitate putting much thought into the implementation, since the numbers are apparently small, it may sometimes be desirable to use an algorithm with a time complexity not essentially dependent on the number of items, e. g.:
import numpy as np
def dist(inp):
inp = np.array(inp)
m = len(inp) # number of buckets
n = sum(inp) # number of items
l = n//m # low number in an output bucket
h = (n+m-1)//m # high number in an output bucket
lo = inp < l # buckets which need transfer to
hi = inp > h # buckets which need transfer from
out = np.empty(m, int)
out[lo] = l # fill underfull buckets with low
out[hi] = h # fill overfull buckets with high
out[~lo & ~hi] = inp[~lo & ~hi] # keep other buckets as is
o = sum(out) # check missing or surplus items
if o < n: out[np.where(out == l)[0][:n-o]] = h # adjust
if o > n: out[np.where(out == h)[0][:o-n]] = l # adjust
return out