40 units at value of 1
10 units at value of 2
10 units at value of 4
60 units total with a value of 100 and an average of 1 + 2/3
Problem: Divide into 2 groups of 30
Group A & B both have 30 units with exactly 1.67 (1 + 2/3)
20 units of 1
5 units of 2
5 units of 4
Now assuming you don't have any bugs in your code and GrandFather used it correctly, it can be shown that it does not always produce optimal results. Update: To give you an idea of how I was going to find such a scenario - see Re: Permutation of groups (and the root thread).
| [reply]
[d/l] |
Yes, indeed - however, my contention here is that this because of the smallest-bucket-first algorithm's failure to take into account relative factorization of buckets and items (see note above)
In Grandfather's example there is no "smallest bucket" so the advantage of size of deviation vs. size of bucket is moot. So yes, the smallest bucket first algorithm is not optimal "as is" - it needs to be modified to consider the case where the the number of items at each deviation from the mean is evenly divisible by the number of same-sized buckets, or some variation on the theme (I haven't really thought through exactly how the algorithm would work in sets more complicated than the one Grandfather presented).
What I was really hoping for was a counter example where the number of items was not divisible by the number of same-sized buckets (as in Grandfather's example). I'm having trouble thinking of one. If such an example exists, there is really not much point in spending time coding up an algorithm that takes into account divisibility of item counts by bucket sizes.
What is bugging me most, is the claim that this problem can't be solved analytically. It is simply not true, if the only correction needed to the smallest-bucket-first algorithm is a few well placed use integer; $items/$buckets or calculations of least or greatest common denominators.
Best, beth
Update: The notion of using the permutation module sounds interesting. I'm wondering if you could explain further? It seems more like it would be useful in checking the result of allocating a particular distribution (by a brute force comparison of the smallest-basket-first algorithm result to all possible solutions) than it would be useful in constructing the particular distribution that would have a sub-optimal result.
| [reply]
[d/l] |
ELISHEVA,
I have provided an example in another post that demonstrates that the algorithm does not always produce optimal results. You asked about how I was going to unrestricted integer partitions and combinatorials to find such an example. In a nutshell, it would be a brute force solution for a given data set to find the optimal solution for all possible groupings.
Let's say for my data set, I generate 12 random values ranging between 15 and 30. First, I need to know every single possible grouping. This can be accomplished using unrestricted integer partitioning (see RFC: Integer::Partition::Unrestricted and Re: Generator of integer partitionts of n for more details). Knowing that 1 possible way of breaking 12 into groups is 6/6 does me no good by itself.
At this point, there are two options. You could generate all possible permutations of the list and then gather them using your integer partition. For instance, if the current iteration of your integer partition were (2, 3, 3, 4) then you would take the first 2, next 3, etc. Determine the averages, get the next permutation, wash rinse repeat. You would use a watermark algorithm to keep track of "best" and you could stop the second you find one that the heuristic solution fails to produce.
Alternatively, you could create an arbitrarily nested loops solution using combinations. You could take each bucket in the unrestricted integer partition iteration and generate all possible combinations - perhaps using Re: Iterating over combinations. You then need to remove those used items from the list to generate the next bucket. This is a wash-rinse-repeat algorithm outlined in Arbitrarily Nested Loops.
Most of this work I had already done in the permutations of groups link I originally pointed to. I hope that explains.
| [reply] |
