Recently I've came across a hard problem solving while doing a project. And I'd like to ask you guys for a solution / algorithm to solve it, because I'm really struggling to think about a clever idea to do so.
I have an arbitrary number of floats:
and one integer:
I need to divide the integer I into the floats as if I was distributing indivisible things. So basically the proportion must hold in some sense, in the sense that the biggest float must get the biggest integer. A good metaphor is as if i'm dividing stocks that can't be split.
If the first investor has 0.6 percent of the stocks and the second has 0.4, given 1 stock to split, i'd give it to the first one (100% 0%). If had 2 stocks, I'd give one to the first and one to the second one (50% 50%). Notice that I always want the split to be as proportional (as close to 60% 40%) as possible.
The problem itself is not terribly defined, but there is some sense of what should happen and what shouldn't. Some examples that easily pop in my mind are:
If: f1 = 0.4, f2 = 0.3, f3 = 0.3, I = 1 then I need f1-result = 1, f2-result = 0, f3-result = 0,
If: f1 = 0.4, f2 = 0.4, f3 = 0.2, I = 1 then I need f1-result = 1, f2-result = 0, f3-result = 0 or f1-result = 0, f2-result = 1, f3-result = 0
If: f1 = 0.6, f2 = 0.25, f3 = 0.15, I = 5 then I need f1-result = 3, f2-result = 2, f3-result = 1.
Here's how I'd approach it, at least initially.
Every bucket has a desired amount that it needs. This is based on their float values, and all the float values sum to 1.
So, go through the "objects" to be distributed one by one. To figure out which bucket gets it, you need to find the bucket that is below its desired amount by the largest differential (just choose the first if there are more than one equally under their desired level). This is the "unhappiest" bucket.
Then you distribute that object to that bucket, adjust the figures and move on to the next object. That means an object is always distributed in such a way to make the lives of the unhappiest buckets a little better (good grief, this sounds like I'm a social worker).
By way of example, let's start distributing objects to three buckets (that want 50%, 30%, and 20% respectively), based on that algorithm described above.
The second figure in the parentheses is the deviation of each bucket from its desired percentage so, at each stage, we choose the bucket which is the furthest below that desired level, the unhappiest (indicated by *):
BucketA (50%) BucketB (30%) BucketC (20%)
------------- ------------- -------------
0 (0%,-50*) 0 (0%,-30) 0 (0%,-20)
1 (100%,+50) 0 (0%,-30*) 0 (0%,-20)
1 (50%,+0) 1 (50%,+20) 0 (0%,-20*)
1 (33%,-17*) 1 (33%,+3) 1 (33%,+13)
2 (50%,+0) 1 (25%,-5*) 1 (25%,+5)
2 (40%,-10*) 2 (40%,+10) 1 (20%,+0)
3 (50%,+0) 2 (33%,+3) 1 (17%,-3*)
3 (43%,-7*) 2 (29%,-1) 2 (29%,+9)
4 (50%,+0) 2 (25%,-5*) 2 (25%,+5)
4 (44%,-6*) 3 (33%,+3) 2 (22%,+2)
5 (50%,+0) 3 (30%,+0) 2 (20%,+0)
Note that the initial condition has all buckets at 0% even though that's not technically correct (it could just as easily be considered 100% or even 3.14159% based on the undefined divide-by-zero nature of the calculation). However, it's a good way to ensure the initial distribution is to the bucket that wants the highest percentage, after which the percentages become well defined.
You can see from that table above that the distribution of objects eventually leads towards the desired outcome.
And, if you want some code you can play with to see this in action (and let's face it, who wouldn't want that?), see the following Python program:
desiredPct = [50, 30, 20]
bucket = [0, 0, 0]
count = 0
# Allocate first item specially so no concern with div-by-zero.
idx = desiredPct.index(max(desiredPct))
happy_min = -desiredPct[idx]
bucket[idx] += 1
count += 1
actualPct = [x * 100 / count for x in bucket]
print "Unhappiest %6.2f @ %d, want %s%%, have %s (%s%%)" % (happy_min, idx, desiredPct, bucket, actualPct)
# Allocate all others in loop.
for i in range(99):
# Get most disadvantaged bucket.
idx = 0
happy_min = bucket[idx] * 100 / sum(bucket) - desiredPct[idx]
for j in range(1, len(bucket)):
happy = bucket[j] * 100 / sum(bucket) - desiredPct[j]
if happy < happy_min:
idx = j
happy_min = happy
bucket[idx] += 1
count += 1
actualPct = [x * 100 / count for x in bucket]
print "Unhappiest %6.2f @ %d, want %s%%, have %s (%s%%)" % (happy_min, idx, desiredPct, bucket, actualPct)
which outputs:
Unhappiest -50.00 @ 0, want [50, 30, 20]%, have [1, 0, 0] ([100, 0, 0]%)
Unhappiest -30.00 @ 1, want [50, 30, 20]%, have [1, 1, 0] ([50, 50, 0]%)
Unhappiest -20.00 @ 2, want [50, 30, 20]%, have [1, 1, 1] ([33, 33, 33]%)
Unhappiest -17.00 @ 0, want [50, 30, 20]%, have [2, 1, 1] ([50, 25, 25]%)
Unhappiest -5.00 @ 1, want [50, 30, 20]%, have [2, 2, 1] ([40, 40, 20]%)
Unhappiest -10.00 @ 0, want [50, 30, 20]%, have [3, 2, 1] ([50, 33, 16]%)
Unhappiest -4.00 @ 2, want [50, 30, 20]%, have [3, 2, 2] ([42, 28, 28]%)
Unhappiest -8.00 @ 0, want [50, 30, 20]%, have [4, 2, 2] ([50, 25, 25]%)
Unhappiest -5.00 @ 1, want [50, 30, 20]%, have [4, 3, 2] ([44, 33, 22]%)
Unhappiest -6.00 @ 0, want [50, 30, 20]%, have [5, 3, 2] ([50, 30, 20]%)
Unhappiest 0.00 @ 0, want [50, 30, 20]%, have [6, 3, 2] ([54, 27, 18]%)
Unhappiest -3.00 @ 1, want [50, 30, 20]%, have [6, 4, 2] ([50, 33, 16]%)
Unhappiest -4.00 @ 2, want [50, 30, 20]%, have [6, 4, 3] ([46, 30, 23]%)
Unhappiest -4.00 @ 0, want [50, 30, 20]%, have [7, 4, 3] ([50, 28, 21]%)
Unhappiest -2.00 @ 1, want [50, 30, 20]%, have [7, 5, 3] ([46, 33, 20]%)
Unhappiest -4.00 @ 0, want [50, 30, 20]%, have [8, 5, 3] ([50, 31, 18]%)
Unhappiest -2.00 @ 2, want [50, 30, 20]%, have [8, 5, 4] ([47, 29, 23]%)
Unhappiest -3.00 @ 0, want [50, 30, 20]%, have [9, 5, 4] ([50, 27, 22]%)
Unhappiest -3.00 @ 1, want [50, 30, 20]%, have [9, 6, 4] ([47, 31, 21]%)
Unhappiest -3.00 @ 0, want [50, 30, 20]%, have [10, 6, 4] ([50, 30, 20]%)
Unhappiest 0.00 @ 0, want [50, 30, 20]%, have [11, 6, 4] ([52, 28, 19]%)
Unhappiest -2.00 @ 1, want [50, 30, 20]%, have [11, 7, 4] ([50, 31, 18]%)
Unhappiest -2.00 @ 2, want [50, 30, 20]%, have [11, 7, 5] ([47, 30, 21]%)
Unhappiest -3.00 @ 0, want [50, 30, 20]%, have [12, 7, 5] ([50, 29, 20]%)
Unhappiest -1.00 @ 1, want [50, 30, 20]%, have [12, 8, 5] ([48, 32, 20]%)
Unhappiest -2.00 @ 0, want [50, 30, 20]%, have [13, 8, 5] ([50, 30, 19]%)
Unhappiest -1.00 @ 2, want [50, 30, 20]%, have [13, 8, 6] ([48, 29, 22]%)
Unhappiest -2.00 @ 0, want [50, 30, 20]%, have [14, 8, 6] ([50, 28, 21]%)
Unhappiest -2.00 @ 1, want [50, 30, 20]%, have [14, 9, 6] ([48, 31, 20]%)
Unhappiest -2.00 @ 0, want [50, 30, 20]%, have [15, 9, 6] ([50, 30, 20]%)
Unhappiest 0.00 @ 0, want [50, 30, 20]%, have [16, 9, 6] ([51, 29, 19]%)
Unhappiest -1.00 @ 1, want [50, 30, 20]%, have [16, 10, 6] ([50, 31, 18]%)
Unhappiest -2.00 @ 2, want [50, 30, 20]%, have [16, 10, 7] ([48, 30, 21]%)
Unhappiest -2.00 @ 0, want [50, 30, 20]%, have [17, 10, 7] ([50, 29, 20]%)
Unhappiest -1.00 @ 1, want [50, 30, 20]%, have [17, 11, 7] ([48, 31, 20]%)
Unhappiest -2.00 @ 0, want [50, 30, 20]%, have [18, 11, 7] ([50, 30, 19]%)
Unhappiest -1.00 @ 2, want [50, 30, 20]%, have [18, 11, 8] ([48, 29, 21]%)
Unhappiest -2.00 @ 0, want [50, 30, 20]%, have [19, 11, 8] ([50, 28, 21]%)
Unhappiest -2.00 @ 1, want [50, 30, 20]%, have [19, 12, 8] ([48, 30, 20]%)
Unhappiest -2.00 @ 0, want [50, 30, 20]%, have [20, 12, 8] ([50, 30, 20]%)
Unhappiest 0.00 @ 0, want [50, 30, 20]%, have [21, 12, 8] ([51, 29, 19]%)
Unhappiest -1.00 @ 1, want [50, 30, 20]%, have [21, 13, 8] ([50, 30, 19]%)
Unhappiest -1.00 @ 2, want [50, 30, 20]%, have [21, 13, 9] ([48, 30, 20]%)
Unhappiest -2.00 @ 0, want [50, 30, 20]%, have [22, 13, 9] ([50, 29, 20]%)
Unhappiest -1.00 @ 1, want [50, 30, 20]%, have [22, 14, 9] ([48, 31, 20]%)
Unhappiest -2.00 @ 0, want [50, 30, 20]%, have [23, 14, 9] ([50, 30, 19]%)
Unhappiest -1.00 @ 2, want [50, 30, 20]%, have [23, 14, 10] ([48, 29, 21]%)
Unhappiest -2.00 @ 0, want [50, 30, 20]%, have [24, 14, 10] ([50, 29, 20]%)
Unhappiest -1.00 @ 1, want [50, 30, 20]%, have [24, 15, 10] ([48, 30, 20]%)
Unhappiest -2.00 @ 0, want [50, 30, 20]%, have [25, 15, 10] ([50, 30, 20]%)
Unhappiest 0.00 @ 0, want [50, 30, 20]%, have [26, 15, 10] ([50, 29, 19]%)
Unhappiest -1.00 @ 1, want [50, 30, 20]%, have [26, 16, 10] ([50, 30, 19]%)
Unhappiest -1.00 @ 2, want [50, 30, 20]%, have [26, 16, 11] ([49, 30, 20]%)
Unhappiest -1.00 @ 0, want [50, 30, 20]%, have [27, 16, 11] ([50, 29, 20]%)
Unhappiest -1.00 @ 1, want [50, 30, 20]%, have [27, 17, 11] ([49, 30, 20]%)
Unhappiest -1.00 @ 0, want [50, 30, 20]%, have [28, 17, 11] ([50, 30, 19]%)
Unhappiest -1.00 @ 2, want [50, 30, 20]%, have [28, 17, 12] ([49, 29, 21]%)
Unhappiest -1.00 @ 0, want [50, 30, 20]%, have [29, 17, 12] ([50, 29, 20]%)
Unhappiest -1.00 @ 1, want [50, 30, 20]%, have [29, 18, 12] ([49, 30, 20]%)
Unhappiest -1.00 @ 0, want [50, 30, 20]%, have [30, 18, 12] ([50, 30, 20]%)
Unhappiest 0.00 @ 0, want [50, 30, 20]%, have [31, 18, 12] ([50, 29, 19]%)
Unhappiest -1.00 @ 1, want [50, 30, 20]%, have [31, 19, 12] ([50, 30, 19]%)
Unhappiest -1.00 @ 2, want [50, 30, 20]%, have [31, 19, 13] ([49, 30, 20]%)
Unhappiest -1.00 @ 0, want [50, 30, 20]%, have [32, 19, 13] ([50, 29, 20]%)
Unhappiest -1.00 @ 1, want [50, 30, 20]%, have [32, 20, 13] ([49, 30, 20]%)
Unhappiest -1.00 @ 0, want [50, 30, 20]%, have [33, 20, 13] ([50, 30, 19]%)
Unhappiest -1.00 @ 2, want [50, 30, 20]%, have [33, 20, 14] ([49, 29, 20]%)
Unhappiest -1.00 @ 0, want [50, 30, 20]%, have [34, 20, 14] ([50, 29, 20]%)
Unhappiest -1.00 @ 1, want [50, 30, 20]%, have [34, 21, 14] ([49, 30, 20]%)
Unhappiest -1.00 @ 0, want [50, 30, 20]%, have [35, 21, 14] ([50, 30, 20]%)
Unhappiest 0.00 @ 0, want [50, 30, 20]%, have [36, 21, 14] ([50, 29, 19]%)
Unhappiest -1.00 @ 1, want [50, 30, 20]%, have [36, 22, 14] ([50, 30, 19]%)
Unhappiest -1.00 @ 2, want [50, 30, 20]%, have [36, 22, 15] ([49, 30, 20]%)
Unhappiest -1.00 @ 0, want [50, 30, 20]%, have [37, 22, 15] ([50, 29, 20]%)
Unhappiest -1.00 @ 1, want [50, 30, 20]%, have [37, 23, 15] ([49, 30, 20]%)
Unhappiest -1.00 @ 0, want [50, 30, 20]%, have [38, 23, 15] ([50, 30, 19]%)
Unhappiest -1.00 @ 2, want [50, 30, 20]%, have [38, 23, 16] ([49, 29, 20]%)
Unhappiest -1.00 @ 0, want [50, 30, 20]%, have [39, 23, 16] ([50, 29, 20]%)
Unhappiest -1.00 @ 1, want [50, 30, 20]%, have [39, 24, 16] ([49, 30, 20]%)
Unhappiest -1.00 @ 0, want [50, 30, 20]%, have [40, 24, 16] ([50, 30, 20]%)
Unhappiest 0.00 @ 0, want [50, 30, 20]%, have [41, 24, 16] ([50, 29, 19]%)
Unhappiest -1.00 @ 1, want [50, 30, 20]%, have [41, 25, 16] ([50, 30, 19]%)
Unhappiest -1.00 @ 2, want [50, 30, 20]%, have [41, 25, 17] ([49, 30, 20]%)
Unhappiest -1.00 @ 0, want [50, 30, 20]%, have [42, 25, 17] ([50, 29, 20]%)
Unhappiest -1.00 @ 1, want [50, 30, 20]%, have [42, 26, 17] ([49, 30, 20]%)
Unhappiest -1.00 @ 0, want [50, 30, 20]%, have [43, 26, 17] ([50, 30, 19]%)
Unhappiest -1.00 @ 2, want [50, 30, 20]%, have [43, 26, 18] ([49, 29, 20]%)
Unhappiest -1.00 @ 0, want [50, 30, 20]%, have [44, 26, 18] ([50, 29, 20]%)
Unhappiest -1.00 @ 1, want [50, 30, 20]%, have [44, 27, 18] ([49, 30, 20]%)
Unhappiest -1.00 @ 0, want [50, 30, 20]%, have [45, 27, 18] ([50, 30, 20]%)
Unhappiest 0.00 @ 0, want [50, 30, 20]%, have [46, 27, 18] ([50, 29, 19]%)
Unhappiest -1.00 @ 1, want [50, 30, 20]%, have [46, 28, 18] ([50, 30, 19]%)
Unhappiest -1.00 @ 2, want [50, 30, 20]%, have [46, 28, 19] ([49, 30, 20]%)
Unhappiest -1.00 @ 0, want [50, 30, 20]%, have [47, 28, 19] ([50, 29, 20]%)
Unhappiest -1.00 @ 1, want [50, 30, 20]%, have [47, 29, 19] ([49, 30, 20]%)
Unhappiest -1.00 @ 0, want [50, 30, 20]%, have [48, 29, 19] ([50, 30, 19]%)
Unhappiest -1.00 @ 2, want [50, 30, 20]%, have [48, 29, 20] ([49, 29, 20]%)
Unhappiest -1.00 @ 0, want [50, 30, 20]%, have [49, 29, 20] ([50, 29, 20]%)
Unhappiest -1.00 @ 1, want [50, 30, 20]%, have [49, 30, 20] ([49, 30, 20]%)
Unhappiest -1.00 @ 0, want [50, 30, 20]%, have [50, 30, 20] ([50, 30, 20]%)
This also shows that, once you get to the desired outcome for the first time, the distribution of objects tends to stay close to what you wanted.