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