Grouping objects by percentages

[Rick Governale]

This is somewhat of a brain teaser that I need for a real application. I'm trying to find an easy way to group items by a varying amount of percentages.

So I have a List of objects that can go from 1 to n objects.

I also have another list of Percentages that add up to 100%.

What I need to do is take my List of objects and separate them into groups based on that percentage.

ArrayList objectList = new ArrayList(100);

ArrayList<Float> percentageList = new ArrayList();

percentageList.add(.10);
percentageList.add(.20);
percentageList.add(.30);
percentageList.add(.40);

So what I would need is my object list divided into 4 groups.
The first group would be 10 percent of the objects, second group would be 20%, third 30%, and fourth 40%.

Anyone know of an easy way to accomplish this? I'm not much for math.

[Paul Clapham]

Originally posted by Rick Governale:
What I need to do is take my List of objects and separate them into groups based on that percentage.

We haven't come to the math yet. (And when we do, it's only going to be the arithmetic you did in elementary school.) First you need to explain how you're going to do that separating. If it helps, do an example. Suppose your list is A, B, C, D, E, and F. And let's stick with 10%, 20%, 30%, and 40% as your percentages. What would be the result of separating those six items into those four groups?

[fred rosenberger]

There are a couple ways, depending on how accurate you need to be.

One way would be to use a random number generator. using your example, create a random number from 1 to 100.

if the number is from 1-10, your object goes in the first group.
from 11 - 30, into group two.
31-60 into group three,
and 61-100 into group four.

for greater accuracy in your distribution, you could go from 1 to 100,000 instead. Of course, there is still a change your objects do not get divided up correctly - all could end in the same group theoretically.


Or you may be able to come up with a hash function of some kind that does something similar.

One question is what do you want to do if you have the percentages like you list, but only have two items? will it be an issue if your actual distribution is way off?

[Rick Governale]

Originally posted by fred rosenberger:
There are a couple ways, depending on how accurate you need to be.

One way would be to use a random number generator. using your example, create a random number from 1 to 100.

if the number is from 1-10, your object goes in the first group.
from 11 - 30, into group two.
31-60 into group three,
and 61-100 into group four.

for greater accuracy in your distribution, you could go from 1 to 100,000 instead. Of course, there is still a change your objects do not get divided up correctly - all could end in the same group theoretically.


Or you may be able to come up with a hash function of some kind that does something similar.

One question is what do you want to do if you have the percentages like you list, but only have two items? will it be an issue if your actual distribution is way off?

It doesn't have to be exactly accurate but it does have to be close enough, simply because it can't be exact when we need to deal with whole numbers.
There is also a very real possibility that that list of object passed will be less than the amount of groups requested to be created. It could only be one object passed in that is requested to be divided into 19 groups. In that case I would have to simply just create the minimum number of groups.

[Paul Clapham]

Oh, I see, your problem is that you don't know how to allocate the objects into the buckets of different sizes and you're looking for suggestions.

But you still need to define "close enough". If you have 10 objects and you want to put them into two buckets which are both defined as 50%, do you absolutely have to end up with 5 objects in each? Or is 4 in one and 6 in the other "close enough"?

[Rick Governale]

Originally posted by Paul Clapham:
Oh, I see, your problem is that you don't know how to allocate the objects into the buckets of different sizes and you're looking for suggestions.

But you still need to define "close enough". If you have 10 objects and you want to put them into two buckets which are both defined as 50%, do you absolutely have to end up with 5 objects in each? Or is 4 in one and 6 in the other "close enough"?

So for close enough I would say, if it can be divided exactly then it should be. If not then it should be as close as possible.

So if there are 100 objects and the percentages are 10%,20%,30%,40% then they should be divided as 10,20,30,40.

However if the are 99 objects, then ideally it would be 10,20,30,39.

If there are only 3 objects, then 1,1,1 would have to suffice.