Unequally distributed quantity

Suppose that you have to divide or to distribute a quantity in three (maybe a rent payment), but you want to do it unequally.

It can be done more or less mentally, but I wanted to have
quickly all the possibilities and decided to write some code to do it.

I though how it is done mentally. For instance, dividing 990 units in 3 parts:

  • You have three parts of 330 each one
  • Subtract 5 to one and add it to another
  • Repeating that you obtain different possibilities to divide initial quantity

Translation to code.

First approximation to the problem was to establish a minimum that each person would pay. Let’s to say 250. 250×3= 750, so it remained 240 units to share out.

I wanted a granularity of 5 units, so there was in fact a 2405=48 items (of 5 units) to share out.

It was not trivial for me to lay out the problem until I realized that this matched with some well known combinatorial problem that I didn’t remember. After a search I found exactly what I was looking for: Start and bars

It can be used to solve many simple counting problems, such as how many ways there are to put n indistinguishable balls into k distinguishable bins.

It can be easily done with Python using combinations function

import itertools

def combinations(n, k):
	return itertools.combinations(range(n), k)

def calculate_rent(n, k):
	for c in combinations(n, k):
		if sum(c)==n:
			yield c

combinations(n,k) return r length subsequences of elements from the input iterable n. Afterwards, we only want subsequences whose sum of the k bins be equal to n.

Just left to write some auxiliary code in order to print the list. Due to what we have obtained is a list of ways  to put n indistinguishable balls (48) into k distinguishable bins (3), it is necessary to multiply each ball by our granularity (5) and sum the minimum.


total = 990
minimum = 250
people = 3
granularity = 5
remain = total - minimum*people
rent_combinations = calculate_rent(remain/granularity,people)
for rents in rent_combinations:
	print([5*i+minimum for i in rents])

Below is displayed a partial screen-shot of the 192 total elements of the output.


No comments yet. Why don’t you start the discussion?

Leave a Reply

Your email address will not be published. Required fields are marked *