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.
|