2

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.

Example:
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]) == [5]
# 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
6
  • 4
    How do you define the "best uniform way"? Are we minimizing the range (max - min) of the final values? Or the standard deviation of the final values? Or their geometric mean?
    – Ixrec
    Jul 28, 2015 at 22:05
  • 1
    Also, what do you mean by "better algorithm"? Better in terms of time complexity, space, resulting in a "better" distribution according to some metric?
    – Hulk
    Jul 29, 2015 at 5:02
  • It may make sense to keep track of some sort of histogramm depending on how many different "fill states" in your target collection you expect - if you can ensure that this histogram-table keeps up to date (all modifying operations on your collection update it too), you wouldn't need to loop through your entire collection when distributing with your _share function.
    – Hulk
    Jul 29, 2015 at 5:12
  • @lxrec Thank you. Edited the problem. Please, suggest more correct name for that.
    – pikerr
    Jul 29, 2015 at 9:15
  • 1
    @lxrec I suppose, we are minimizing the range of the final values just by adding to smallest values from the bottom. We may call it like that.
    – pikerr
    Jul 29, 2015 at 11:09

1 Answer 1

1

I made a slightly different algorithm:

def share(available, members):

    # find across how many members we must distribute and what the total sum of those values is
    total = available
    for idx, member in enumerate(members):
        total += member
        count = idx+1
        if (idx >= len(members)-1):
            break
        if (total / (idx+1) <= members[idx+1]):
            break

    # distribute the total value among 'count' first value
    distr = []
    for member in members[0:count]:
        target = total//count
        diff = target - member
        distr.append(diff)

        total -= target
        count -= 1

    return distr

It works in two steps. First step calculates across how many members the available value needs to be distributed along with total sum of all those values after being distributed.

In the second step, the differences are calculated based on value that would be if it was distributed.

But handling the edge cases complicates the whole algorithm.

4
  • Great! Thank you, @Euphoric. Exactly what I was looking for.
    – pikerr
    Jul 29, 2015 at 12:44
  • Seems that is has some excessive logic in 2nd part. Why we can't just find out the target once and then just calculate the diff for each member?
    – pikerr
    Jul 31, 2015 at 17:18
  • @pikerr The diff needs to take into account that the division might not end up as integer. The additional logic is there to ensure output is not fractional, but total is still correct.
    – Euphoric
    Jul 31, 2015 at 18:10
  • Yes, I see. I enhanced your solution, making it more flexible. You can choose strict_equal mode now. Updated my question.
    – pikerr
    Jul 31, 2015 at 19:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.