CODEWITHSUNDEEP
algorithmmathdistributionbuckets
msbware
msbware

Reputation: 23

Algorithm to calculate weighted distribution ratio

Here's the problem I'm facing. I have some number of items. I then have a varying number of buckets with a weight (between 0 and 1) attached to them. I'm trying to calculate the percentage of the items that should go in each bucket.

For example, let's say I have 20 items and 3 buckets:

The percentage would then be:

The percentage should add to 100% so that all items will be distributed into buckets. In the example above, B1 and B2 should both have twice as many items as B3 since their weight is double that of B3; but, when all 3 buckets are put together, the actual percentage of items B1 gets is 40%.

Is there an algorithm already out there for this or do any of you have an idea of how to solve it?

Upvotes: 1

Views: 2862

Answers (2)

Tim Biegeleisen
Tim Biegeleisen

Reputation: 522636

I think you can just divide the weight of each bucket by the total weight of all items to find the percentage of items which each bucket should bear.

However, there is a slight issue should the number of items and bucket weights not divide evenly. For the sake of example, let's consider the following scenario:

B1 - weight: 0.15
B2 - weight: 0.15
B3 - weight: 0.70

And let us suppose that there are 23 items.

Then we can compute the number of items which should be allocated to each bucket by just multiplying the fraction of total weight against the total number of items:

B1 - weight: 0.15, 3.45 items
B2 - weight: 0.15, 3.45 items
B3 - weight: 0.70, 16.1 items

One algorithm which could deal with this fractional bucket problem would be to compute the number of items for each bucket, one at a time, and then shift the remainder to the next calculation. So, in this example, we would do this:

B1 - 3.45 items, keep 3, rollover 0.45
B2 - 3.45 items + 0.45 = 3.9 items, keep 3, rollover 0.9
B3 - 16.1 items + 0.9 = 17 items (whole number, and last bucket)

Upvotes: 5

slash_rick_dot
slash_rick_dot

Reputation: 923

Sum the weights from all buckets, then divide each bucket's weight by that sum to derive the bucket's percentage of the total.

Upvotes: 1

Related Questions