Need some help with an algorithm, math heavy. Not homework. :P

[ZaneNBK]

Hopefully someone here will have a clue, I've done some searching for numerical distribution formulas but that's a pretty broad categroy. I have multiple numerical buckets (not a set number, it can change each time I run this process) with diffent values in each. I need to add a specific number (that also can change from run to run) spread out evenly so that the buckets with the least are filled up first. The trick is that I'd like to be able to calculate them all at once or a single calculation per bucket. I can easily allocate one at a time (I'm working with whole numbers, but I can do rounding at the end if I need to) and do this, but that is very very slow for the ammount of data I'm looking at. Here's an example:

Bucket 1: 10
Bucket 2: 3
Bucket 3: 4
Bucket 4: 7

Quantity to allocate: 10

Result:

Bucket 1: 10 (+0)
Bucket 2: 8 (+5)
Bucket 3: 8 (+4)
Bucket 4: 8 (+1)

Anyone have any suggestions or any useful links for me? I have some experience with Calculus. What I'm looking for is a formula or data-set algorithm for doing this without looping. At the worst I could loop through the buckets once and run a calculation per bucket, that won't be too slow.

Thanks.

 

[hdeck]

my head hurts

 

[SoylentGreen]

24.69

 

[ZaneNBK]

Originally posted by: Kiyup
24.69

When I try it your way I keep getting 47.59... WTH?

 

[atom]

Do you know how many you are allocating at any given time? If so, why not just add and divide?

IE. 10+3+4+7+10= 34

34/4=8.5 rounded down = 8

So at least all buckets have to have 8 in each. Allocate so that each bucket has at least 8 each and if there are leftovers put in a bucket that has 8.

 

[Barnaby W. Füi]

Do one at a time, add them all up and divide the current one by the total, then based on that determine how much to put in that one.

That's about the best I can come up with

percent = 1 - (current_bucket / (a+b+c+d) )

current_bucket = current_bucket + (total_available * percent)

something like that i suppose...

 

[ZaneNBK]

Originally posted by: atom
Do you know how many you are allocating at any given time? If so, why not just add and divide?

IE. 10+3+4+7+10= 34

34/4=8.5 rounded down = 8

So at least all buckets have to have 8 in each. Allocate so that each bucket has at least 8 each and if there are leftovers put in a bucket that has 8.

Sorry, but it's not that simple. Change the first bucket to 25 and try that. 25+3+4+7+10 = 49, 49/4=12.25 which isn't possible since I can take pre-existing quantity out of one bucket and put it into another. Thanks though.

 

[ZaneNBK]

Originally posted by: BingBongWongFooey
Do one at a time, add them all up and divide the current one by the total, then based on that determine how much to put in that one.

That's about the best I can come up with

percent = 1 - (current_bucket / (a+b+c+d) )

current_bucket = current_bucket + (total_available * percent)

something like that i suppose...

With your calculation bucket A would be getting some of the 10 I'm allotting, and it shouldn't be.

 

[atom]

Originally posted by: ZaneNBK

Originally posted by: atom
Do you know how many you are allocating at any given time? If so, why not just add and divide?

IE. 10+3+4+7+10= 34

34/4=8.5 rounded down = 8

So at least all buckets have to have 8 in each. Allocate so that each bucket has at least 8 each and if there are leftovers put in a bucket that has 8.

Sorry, but it's not that simple. Change the first bucket to 25 and try that. 25+3+4+7+10 = 49, 49/4=12.25 which isn't possible since I can take pre-existing quantity out of one bucket and put it into another. Thanks though.

Oops. LOL. Misunderstood your problem.

 

[Barnaby W. Füi]

Originally posted by: ZaneNBK

Originally posted by: BingBongWongFooey
Do one at a time, add them all up and divide the current one by the total, then based on that determine how much to put in that one.

That's about the best I can come up with

percent = 1 - (current_bucket / (a+b+c+d) )

current_bucket = current_bucket + (total_available * percent)

something like that i suppose...

With your calculation bucket A would be getting some of the 10 I'm allotting, and it shouldn't be.

hmm yeah.. lemme think a little more..

 

[Barnaby W. Füi]

Is this code you are working on? If so, what language?

 

[ZaneNBK]

It's part of a stored procedure (Oracle, PL/SQL). I'm trying to allocate a set quantity of a product to several vendors basically. I need to allocate in such a way that the vendors with the lowest stock get quantity first and it fills them up kind of like filling cone with water.

Here's another sample of data that should test any good formula or algorithm:

Bucket quantities:

5,000,000
3
4
7
3,950
8
12

Ammount to allocate: 10

End result:

5,000,000
8
8
8
3,950
8
12

Have fun, I am.

 

[Barnaby W. Füi]

Originally posted by: ZaneNBK
It's part of a stored procedure (Oracle, PL/SQL).

Hm, I don't really know much about sql math operations, for example, is it even possible to find the smallest or largest values, or anything of the sort? Or is it pretty much just "here's the numbers, that's all you get to work with"?

 

[ZaneNBK]

Hmm... Possible solution:

Starting buckets:

5,000,000
3
4
7
5,000
8
9

1) If the bucket is greater than the quantity I'm allocating then discard it.

New buckets:

3
4
7
8
9

2) Calculate average with allocation quantity added in (but still divide by 5 buckets): 3+4+7+8+9+10(alloc)=41/5=8.2
3) Discard buckets over this average.

New buckets:

3
4
7
8

4) Calculate new average with allocation quantity added in: 3+4+7+8+10=32/4=8 - this is the new target.
5) Set all buckets < 8 to 8.

Can anyone show me a data set that would prove this wrong? Testing in Excel now.

Thanks.

 

[atom]

Part 1 doesn't work because what if you have buckets

A. 10
b. 12
C. 9
D. 10

And you need to allocate 5. Then nothing would be allocated.

When you say this:

I have multiple numerical buckets (not a set number, it can change each time I run this process) with diffent values in each

Are you saying you can dynamically add buckets? Or are you saying at the start of each run you can specify any number of buckets? It's very similar to a basic load balancing algorithm, I'm trying to find that's simple enough for your problem.

 

[Savarak]

Originally posted by: ZaneNBK
It's part of a stored procedure (Oracle, PL/SQL). I'm trying to allocate a set quantity of a product to several vendors basically. I need to allocate in such a way that the vendors with the lowest stock get quantity first and it fills them up kind of like filling cone with water.

Here's another sample of data that should test any good formula or algorithm:

Bucket quantities:

5,000,000
3
4
7
3,950
8
12

Ammount to allocate: 10

End result:

5,000,000
8
8
8
3,950
8
12

Have fun, I am.

hmm, the algorithm gets more fun when you change the originating buckets out of order, like this...:
5,000,000
5
8
3950
7
12
3

unless when you divide the number to allocate such that you have a cut-off, or minimum, to allocate to
...i.e.

5,000,000
533
82
3950
713
12
344
need to allocate 100, with stock at minimum at 100
so the algorithm needs to just pull off 82 and 12, and then with at least 18 units to 82, and at least 88 units to 12
of course, 18+88 isn't 100, so take off a unit each (for buckets corresponding to those that currently have the 82 and 12), so that in the end, to allocate 100 units, there will 15 for the bucket with 82, and 85 for the bucket with 12...
5,000,000
533
97
3950
713
97
344

but then, if it is dealing with some sort of stock... economically the bucket that had 12, should be alloted all 100 units because it likely has the fastest turnaround rate, meaning it probably sells faster than the rest....

ok now my head hurts

 

[br0wn]

How about this:
Let say the amount to allocate is K.

Step 1:
Compute the sum of all the buckets with amount less than K (also add K) and compute the average (divide sum by the number of
buckets with amount less than K).

Step 2:
For all the buckets with amount less than K, add quantities until they are equal the average
computed in Step 1, and put the remaining in the bucket with the least quantity.

For your example:

Bucket quantities:

5,000,000
3
4
7
3,950
8
12

Ammount to allocate: 10

K = 10, then sum = 3+4+7+8+10 = 32.
average = 32/4 = 8 and remain = 0.

Result:
5,000,000
8 (+5)
4 (+4)
7 (+1)
3,950
8
12

 

[Reel]

worst fit

try reading up on that. it may not be exactly what you want but the generic procedure is to use a heap to pull out the bin with the most available space and put the next item into it. I have some java code that may or may not work for you. I am not too sure that what you are requesting of a single calculation is possible, at least not with the best solutions since these problems tend to be NP-hard.

 

[atom]

Still doesn't work. What if you have buckets:

a. 5,000,000
b. 5,000
c. 4,997
d. 4,996

You need to allocate 4,999. Nothing would be allocated to bucket b when there should be quantities allocated to it.

 

[Ameesh]

so you want to have all the buckets have the numerical average or as clse to it as possible

Bucket 1: 75
Bucket 2: 43
Bucket 3: 37
Bucket 4: 19

this will be a little more work if the number of buckets change during runtime but not much.

//calculate these when you start your program for the first time.
int numBuckets = 4; //number of buckets.
int totalAllocated = 174; // 75 + 43 + 37 + 19

Items to add: 630

int currentAverage = ( totalAllocated + Items to add ) / numBuckets; //this number will get updated with every call to add more items in the buckets
totalAllocated += Items to add;

// O(n) and theta(n) here

for (int i = 0; i < numBuckets; i++)
{
numBuckets [ i ] += currentAverage - numBuckets [ i ] // make sure to check before hand if bucket is greater then average if your not allowed to move items from bucket to bucket after the intial move
}




you should get the idea from this. let me know if you have any questions .

the running time is linear and bound to the number of buckets you have which you cant really make any better then that.

 

[Armitage]

You could take a greedy algorithm approach ... sort the list in ascending order and allocate from the beginning of the list until you use up your quantity. Could set some desired inventory level, and, starting at the bottom, fill everyone up to that level until you run out.

 

[br0wn]

Ah you guys are right! Tougher than what I thought.

Let me propose a modification to the algorithm then:

K = quantity to allocate

Step 1:
Sort the buckets so it will be in increasing order.

Step 2:
I'll illustrate Step 2 with a code (the idea here is to find how many buckets should I sum together):

Initialization:
sum = <bucket 0> + K
i=1
average = sum

loop until average < K
{
sum = sum + <bucket i>
i = i+1
average = sum / i
remain = sum % i
}

Step 3:

For all bucket from 0 to i, add them till they are equal to average in Step 2, put remain in the bucket with least quantity

Analysis:
Step 1: O( n log n)
Step 2: O (n)
Step 3: O (n)
Total = O(n log n)



Ameesh: your method doesn't work (reason, look at prev post).

 

[ZaneNBK]

Ameesh, your algorithm doesn't work if some of the buckets have quantities WAY over the total average (average of buckets + quantity to allocate added in before dividing).

ergeorge, that method is the direct method but is too slow unfortunately.

Ok, how about this. My current code does something like it but I was worried that it would trim off too much. I just realized that it should be impossible to trim off too much with this algorithm:

Buckets:

a. 5,000,000
b. 5,000
c. 4,997
d. 4,996
e. 11,000
f. 5,006

Qty to alloc: 10

1) Calculate average with alloc included. (5,000,000 + 5,000 + 4,997 + 4996 + 11,000 +5,006 + 10) / 6 = 838501.5
2) Drop buckets higher than the average.

3) Repeat 1 and 2 until all buckets are below the average with the alloc quantity added in. Stepping through this would look like this:

New buckets after first drop:

a) 5000
b) 4997
c) 4996
d) 11000
e) 5006

Average (alloc included) = 6201.8

New buckets after second drop:

a) 5000
b) 4997
c) 4996
d) 5006

Average (alloc included) = 5002.25

Final set of buckets:

a) 5000
b) 4997
c) 4996

Average (alloc included) = 5001

4) Set each bucket equal to the average.

5) Round (I have special criteria for this and won't cover it here).

I was doing this before but I was only cutting off buckets with quantities 10% greater than the average because I was worried about another part of my process that puts a cap on buckets. Now I move on to part 2, including the caps.

Right now we're running without the artificial caps and this simple algorithm will work. Wish I'd rexamined my previous work more closely. Thanks for all the input guys.

 

[Ameesh]

ahh good point but then you just deviate slightly on how you calculate your average and not include buckets that are not within ohh say +1 standard deviation. that should kill all the buckets that are really high like 5,000,000 and 3,750

 

[ZaneNBK]

With the method I just posted I might have to recalc that average and cut buckets several hundred times (up to a max of about 1000 times), but when the calculation for that is so quick it's no problem to repeat that much. It's much faster than spreading to buckets one at a time (compared to the slowness of sorting a list of up to 1000 buckets up to 4000 times).