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.

def reduce_ratio(load_list, total_num, min_num=1):
  """
  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]
  """
  num_loads = [ [load, min_num] for  load in load_list ]
  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 = min(num_loads, key=lambda (load, count): (float(count)/load, load))
    min_elem[1] += 1
  reduced_loads = map(itemgetter(1), num_loads)
  if sum(reduced_loads) != total_num:
    raise Exception('Could not split loads to required total')
  return reduced_loads

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 :

if not load_list:
    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 :

num_loads = [ [load, 0] for  load in load_list ]
for _ in range(total_num):
    min_elem = min(num_loads, key=lambda (load, count): (float(count)/load, load))
    min_elem[1] += 1
reduced_loads = [num for _,num in num_loads]
assert(sum(reduced_loads) == total_num)
return reduced_loads

• 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.

StackExchange Code Review Q#46226, answer score: 4