Subdivide integers using a given ratio without producing floats

Question

I need to subdivide a given amount of items (lets say 10) using a given ratio [0.55, 0.45]. The result here should either be 6:4 or 5:5. The usual approach [0.55*10, 0.45*10] would result in [6, 5] (11, not 10).

Another example: divide 7 using ratio: [0.36, 0.44, 0.07, 0.07, 0.03, 0.03] which ideally should yield something like [3, 3, 1, 0, 0, 0] or [3, 3, 0, 1, 0, 0].

What would be a good approach to this problem?

Have you attempted to solve this problem? If you have, please edit your question to include your code and research to show what hasn't worked for you. If you haven't, you should attempt to solve it yourself first and then post the code and research here. It makes your question easier for others to answer too! — SuperBiasedMan, Dec 08 '15 at 12:59
See this [stackoverflow](http://stackoverflow.com/questions/2356501/how-do-you-round-up-a-number-in-python) and this [python math](https://docs.python.org/2/library/math.html) — Jose Rocha, Dec 08 '15 at 13:00
I could write something that after doing it as in the first example, ending up with [6,5] would measure if there are more or less in it and then simply, if more, delete one from the highest number or, if less, add to the highest ratio that does not have anything yet. However I was wondering if there is some smart mathematical way to do this. — SecondLemon, Dec 08 '15 at 13:03
@Jose Rocha How would using the ceil function work? If you look at [0.55*10, 0.45*10] it would result in [6,5] with round or ceil either way. I can't manually define if it should round up or down since the ratio is not always made up of 2 numbers. — SecondLemon, Dec 08 '15 at 13:08
"would result in `[6, 5]`" - Nope. "should yield *something like*" - oh come on, don't be sloppy. — Karoly Horvath, Dec 08 '15 at 13:09
Go to [repl](https://repl.it/languages/python3) and write `a = [0.55, 0.45]` next `round(a[1]*10)` next `round(a[0]*10)` and it will give `6` and `4`, what can i do more for you? — Jose Rocha, Dec 08 '15 at 13:17
@Jose Rocha Is this different for python 3 compared to 2.7? `>>> round(0.45*10) 5.0` I guess it is: https://repl.it/B6rG/0 — SecondLemon, Dec 08 '15 at 13:23
[2.7 round](https://docs.python.org/2/library/functions.html#round) vs [3 round](https://docs.python.org/3/library/functions.html#round) seems to me that they are the same. — Jose Rocha, Dec 08 '15 at 13:25
Well I don't know what is happening then. See my previous link (https://repl.it/B6rG/0) I get 5.0 and 6.0 for sure (as should be of course). — SecondLemon, Dec 08 '15 at 13:28
`import math` `a = [0.55, 0.45]` `print math.floor(a[1]*10)` `print math.floor(a[0]*10)` this works for you? — Jose Rocha, Dec 08 '15 at 13:30
Well then I get 4 and 5 respectively (as expected). So not right. — SecondLemon, Dec 08 '15 at 13:31

Iggy · Answer 1 · 2015-12-08T14:13:48.030

2

I would suggest you to have another array. I'm beginner in Python.

Here is the code with your example (you can simply adapt it, I'm sure) :

a = [0.36, 0.44, 0.07, 0.07, 0.03, 0.03]

numberItem = 7
remainder = numberItem


b = [0,0,0,0,0,0]

for i in range(0,6):
    b[i] = round(a[i]*numberItem)
    if (b[i] > remainder) or (b[i] == 0):
        b[i] = remainder
        remainder = 0
    else:
            remainder = remainder - b[i]
    print(b[i])

With this bounds, you cannot have more items than stated. It's better if the ratio array is sorted from the bigger to the smaller.

edited Dec 08 '15 at 14:13

answered Dec 08 '15 at 13:59

Iggy

53
7

Wow... Also very nice. Almost a shame I gave away the answer already. Let me test this a bit. – SecondLemon Dec 08 '15 at 14:15
It is also very nice and good. However Maciek's answer seems a bit more acurate. If you look at this example: 16 samples with ratio [0.47, 0.24, 0.16, 0.13] your algorithm returns [8,4,3,1] and Maciek's [8,4,2,2]. A nice approach though! – SecondLemon Dec 08 '15 at 14:21
I've seen the Maciek algorithm after, and it seems more complete :-) – Iggy Dec 08 '15 at 14:24

Maciek · Accepted Answer · 2015-12-08T14:08:49.950

Here's my try on the matter :) The hardest part being reversing the sort operation and matching it with results... If you don't need to keep the original order of ratios, then you can delete part of the last function.

def scale_ratio(ratios: list) -> list:
    sum_ = sum(ratios)
    return [x/sum_ for x in ratios]

def ratio_breakdown_recursive(x: int, ratios: list) -> list:
    top_ratio = ratios[0]
    part = round(x*top_ratio)
    if x <= part:
        return [x]
    x -= part
    return [part] + ratio_breakdown_recursive(x, scale_ratio(ratios[1:]))


def ratio_breakdown(x: int, ratios: list) -> list:
    sorted_ratio = sorted(ratios, reverse=True)
    assert(round(sum(ratios)) == 1)
    sorted_result = ratio_breakdown_recursive(x, sorted_ratio)
    assert(sum(sorted_result) == x)
    # Now, we have to reverse the sorting and add missing zeros
    sorted_result += [0]*(len(ratios)-len(sorted_result))
    numbered_ratios = [(r, i) for i, r in enumerate(ratios)]
    sorted_numbered_ratios = sorted(numbered_ratios, reverse=True)
    combined = zip(sorted_numbered_ratios, sorted_result)
    combined_unsorted = sorted(combined, key=lambda x: x[0][1])
    unsorted_results = [x[1] for x in combined_unsorted]
    return unsorted_results

Results:

ratio_breakdown(7, [0.36, 0.44, 0.07, 0.07, 0.03, 0.03])
[3, 3, 1, 0, 0, 0]
ratio_breakdown(10, [0.55, 0.45])
[6, 4]
ratio_breakdown(16, [0.16, 0.47, 0.13, 0.24])
[2, 8, 2, 4]

EDIT: That's Python3.

Thanks, looks promising. Let my study it for a while and I report back to you. (doesn't matter if it is in 3 or 2.7) — SecondLemon, Dec 08 '15 at 13:55
I have a bit of a hard time understanding what is going on sometimes but I get the gist of it. However what is happening here (another example): `ratio_breakdown(16, [0.16, 0.47, 0.13, 0.24]) --> [2, 3, 3, 8]` — SecondLemon, Dec 08 '15 at 14:03
I forgot to pass the sorted version of ratios to the recursive function :) Also, changed `math.ceiling` to `round`, it gives nicer results now I guess. — Maciek, Dec 08 '15 at 14:12
Very nice. You seem to have solved it. A well deserved upvote and accept! Thanks a lot. — SecondLemon, Dec 08 '15 at 14:13

Subdivide integers using a given ratio without producing floats

2 Answers2