CODEWITHSUNDEEP
algorithm
Jeff
Jeff

Reputation: 978

Python(/C/Java): How do I divide an integer by an integer, and produce an evenly distributed list of integers?

I have an integer amount of 'somethings', and I want to divide them into groups, each of an integer amount. Not only that, they must be distributed as evenly as possible.

So, let us say for example I have 9 apples (apples = 9) and I need to separate them into 6 groups (groups = 6). And, let us say that I can't cut an apple, so apples/groups = 1.5 and thus a set of groups [1.5, 1.5, 1.5, 1.5, 1.5, 1.5] will not work. One solution would be [2, 2, 2, 1, 1, 1] or similar. But I need them distributed as evenly as possible, thus the solution must be [2, 1, 2, 1, 2, 1]. Or if it was 7 apples into 5 groups, the solution would be [2, 1, 2, 1, 1].

I am aware that you could find different 'even' distributions, say [1, 2, 1, 2, 1, 2] in the case of 9 apples into 6 groups. But since neither is more evenly distributed, either will do. I simply chose, for the sake of argument, to start with the higher number and alternate as long as possible.

How do I find the solution, given the starting amount and the number of groups I want? [I prefer python, but I understand Java/C/C++, so any will do.]

Background: Since I seem to be getting alot of flack for asking this, here is the reason: I am writing a custom text renderer, and I need to lay out justified text. This means adding and integer amount of pixels to the spacing between words, as evenly as possible. And as fast as possible...

Upvotes: 2

Views: 832

Answers (2)

soulcheck
soulcheck

Reputation: 36777

You divide them into to equal groups and add each remainding element to different group until you run out of elements. Ruling out permutations that's an even distribution. If the order is important then having n elements and k groups add each element from the n % k remainding elements to every n / (n % k) th group. That's as even as it gets.

You really don't need any special tools to do this.

edit: This can be done while processing the original list and so that it maintains the order. Basically every n / (n % k) sublist has to have n / k + 1 elements. caf's solution is cleaner though.

Upvotes: 2

caf
caf

Reputation: 239181

If you go through the locations one-by-one, at each allocating the fairest split of the remaining objects, you will get the distribution you want. For your 9 objects into 6 locations example, this goes:

9 ÷ 6 = 1.5, so allocate 2 apples to the first location (rounds up).

7 ÷ 5 = 1.4, so allocate 1 apple to the second location (rounds down).

6 ÷ 4 = 1.5, so allocate 2 apples to the third location (rounds up).

4 ÷ 3 = 1.33.., so allocate 1 apple to the fourth location (rounds down).

3 ÷ 2 = 1.5, so allocate 2 apples to the fifth location (rounds up).

1 ÷ 1 = 1, so allocate 1 apple to the sixth location.

To get the rounded division of a ÷ b from C's truncating integer division, you can use (a + b/2) / b as long as the summation won't overflow.

Upvotes: 14

Related Questions