Utility function to split a number into n parts in the given ratio

I wrote a small utility function that divides a total into n parts in the ratio given in load_list. Numbers in each part should be positive integers. It supports an optional min_num argument that, when specified, puts at least min_num in each of the n parts before distributing the rest. Please review.

"""
Returns the distribution of total_num in the ratio of load_list in the best possible way
min_num gives the minimum per entry
>>> reduce_ratio([5, 10, 15], 12)
[2, 4, 6]
>>> reduce_ratio([7, 13, 30], 6, 0)
[1, 2, 3]
>>> reduce_ratio([7, 13, 50], 6)
[1, 1, 4]
>>> reduce_ratio([7, 13, 50], 6, 3)
Traceback (most recent call last):
...
ValueError: Could not satisfy min_num
>>> reduce_ratio([7, 13, 50], 100, 15)
[15, 18, 67]
>>> reduce_ratio([7, 13, 50], 100)
[10, 19, 71]
"""
yet_to_split = total_num - ( len(num_loads) * min_num )
if yet_to_split < 0:
raise ValueError('Could not satisfy min_num')
for _ in range(yet_to_split):
min_elem[1] += 1
raise Exception('Could not split loads to required total')

Because the problem is not quite formalised and is mostly defined by the way your code currently works, I must confess that I find it quite hard to make thinds more efficient/concise.

A few point however:

• using ( len(num_loads) * min_num ) un-necessarly relies on the way you have populated num_loads. You could something more generic like : yet_to_split = total_num - sum(num for _,num in num_loads) so that things work no matter what.
• at the moment, I don't think it is possible for the condition sum(reduced_loads) != total_num to be true. Indeed, at the beginning, the definition of yet_to_split leads to the following property : yet_to_split + sum_of_loads = total_num. Then as we iterate over yet_to_split, sum_of_loads gets increased one by one. Because the condition cannot be true, it's not really wise to expect anyone to expect and catch this exception. If you want to perform the verification, assert is what you should be using : assert(sum(reduced_loads) == total_num).
• in order to avoid any troubles while processing the input, you might want to add more checks.

My suggestions are the following :

raise ValueError('Cannot distribute over an empty container')
if any(l <= 0 for l in load_list):
raise ValueError('Load list must contain only stricly positive elements')
• A bit of a naive question but couldn't the min_num logic be extracted out by processing the load_list normally and only at the end (in a potentially different function) check that min(return_array) >= min_num ? This makes performance slightly worse for cases leading to failures but makes this usual case a bit clearer.

For instance, the code would be like :

for _ in range(total_num):
min_elem[1] += 1
• Just a suggestion but instead of recomputing the minimal element by reprocessing the whole array every-time, maybe you could use an appropriate data structure like heapq to get the minimal element quickly and then re-add it to the structure once updated.

So in terms of code layout this is a little hard to follow, but apart form that is fine and the docstring is good. However, I'm not sure that your code gives the right result. Also it could also be sped up by at least a factor of four.

Take the example:

In [22]: reduce_ratio([1,50,23],32,6)
Out[22]: [6, 18, 8]

so the first thing the code should do is put 6 in each output as this is min_num, this should give:

[6, 6, 6]

So this removes 3*6=18 from total_num leaving 14 to distribute according to your load_list.

This gives:

Out[3]: [0.1891891891891892, 9.4594594594594597, 4.3513513513513518]

Now obviously 0.1891891891891892 rounds to zero, so we pop that from the list and move on. We now have to split 14 with load_list=[50,23]. This gives:

Out[6]: [9.5890410958904102, 4.4109589041095889]

Rounding this obviously gives [10,4]. So we have successfully split the number 14 into [0,10,4] with load_list=[50,23]. Adding this to our list of min_num ([6,6,6]) gives:

[6, 16, 10]

and [6, 16, 10] != [6, 18, 8].

Apologies if I have missed something in the code and [6, 18, 8] was the desired result. Below is the code I used to get my answer:

output = [min_num for _ in load_list]
total_num -= sum(output)
if total_num < 0:
raise Exception('Could not satisfy min_num')
elif total_num == 0:
return output

output[ii] += value
total_num -= value
return output

This code also has some speed benefits over your current implementation:

In [2]: %timeit reduce_ratio([1,50,23],32,6)
10000 loops, best of 3: 44 us per loop

In [3]: %timeit new_reduce_ratio([1,50,23],32,6)
100000 loops, best of 3: 9.21 us per loop

here we get a speed up of a factor of ~4.8.

• I think OP's code chooses 18 and 8 because 50/18 is approximately equal to 23/8. Commented Apr 4, 2014 at 12:03
• Disclaimer : I have no idea what I am doing. I have defined the 2 following functions to compare results - this is pretty arbitrary so one shouldn't rely too much on its results : def normalise(l): return [float(e)/min(l) for e in l] ; def evaluate_ratio(l1,l2): return sum((e1-e2)**2 for e1,e2 in zip(normalise(l1),normalise(l2))) and I get : evaluate_ratio([1,50,23],[1,50,23]) -> 0.0 evaluate_ratio([1,50,23],[6,16,10]) ->2695.5555555555557 evaluate_ratio([1,50,23],[6,18,8]) -> 2678.4444444444443 so this might be a justification for OP's results anyway. Have my upvote anyway! Commented Apr 4, 2014 at 12:09
• @JanneKarila I agree. I can see how the result is obtained, I'm just not sure it is the right way to do it. Commented Apr 4, 2014 at 12:13
• @Josay: The OP says that you first put min_num in each output and then distribute what remains from total_num. So really you should be evaluating evaluate_ratio([1,50,23],[0,10,4]) and evaluate_ratio([1,50,23],[0,12,2]) Commented Apr 4, 2014 at 12:25
• Indeed, that's a way to see it (even though it would make my functions crash :'(). Commented Apr 4, 2014 at 12:39